論文

査読有り
2018年5月17日

Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error

Physical Review Letters
  • Keisuke Fujii
  • ,
  • Hirotada Kobayashi
  • ,
  • Tomoyuki Morimae
  • ,
  • Harumichi Nishimura
  • ,
  • Shuhei Tamate
  • ,
  • Seiichiro Tani

120
20
開始ページ
200502:1
終了ページ
200502:6
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1103/PhysRevLett.120.200502
出版者・発行元
American Physical Society

The one-clean-qubit model (or the deterministic quantum computation with one quantum bit model) is a restricted model of quantum computing where all but a single input qubits are maximally mixed. It is known that the probability distribution of measurement results on three output qubits of the one-clean-qubit model cannot be classically efficiently sampled within a constant multiplicative error unless the polynomial-time hierarchy collapses to the third level [T. Morimae, K. Fujii, and J. F. Fitzsimons, Phys. Rev. Lett. 112, 130502 (2014)PRLTAO0031-900710.1103/PhysRevLett.112.130502]. It was open whether we can keep the no-go result while reducing the number of output qubits from three to one. Here, we solve the open problem affirmatively. We also show that the third-level collapse of the polynomial-time hierarchy can be strengthened to the second-level one. The strengthening of the collapse level from the third to the second also holds for other subuniversal models such as the instantaneous quantum polynomial model [M. Bremner, R. Jozsa, and D. J. Shepherd, Proc. R. Soc. A 467, 459 (2011)PRLAAZ1364-502110.1098/rspa.2010.0301] and the boson sampling model [S. Aaronson and A. Arkhipov, STOC 2011, p. 333]. We additionally study the classical simulatability of the one-clean-qubit model with further restrictions on the circuit depth or the gate types.

リンク情報
DOI
https://doi.org/10.1103/PhysRevLett.120.200502
ID情報
  • DOI : 10.1103/PhysRevLett.120.200502
  • ISSN : 1079-7114
  • ISSN : 0031-9007
  • SCOPUS ID : 85047381205

エクスポート
BibTeX RIS