量子コンピュータは容易に古典コンピュータをエミュレートすることが可能であるため、古典コンピュータで速く解ける問題（汎用問題）は、量子コンピュータでも同程度以上に速く解くことができる。よって汎用問題について、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。ただし、同程度は可能だとしても、「より大きい」かどうかはよくわかっていない。

量子コンピュータに関係する複雑性クラスにBQPがありBQPはPを包含する。BQPとNPの関係は明確ではないが、BQPとNPは包含関係にないだろうと考えられている。
実際[ソースを編集]

Googleは量子ゲートマシンの高速性が2017年末までに実証されると予想した[83]。古典コンピューターよりも実際の量子ゲートマシンの方が高速に解ける問題が存在することを、量子超越性と呼び、このような問題の探索が続けられている。2019年10月23日、Googleは、ランダムに作った量子回路の出力結果を推定すると言う問題で、量子超越性を実証したと発表した[84]。

量子ゲートマシン上で素因数分解を行うショアのアルゴリズムは、2001年にIBMが世界で初めて15(=3×5)の分解に成功した[20]。2012年にブリストル大学が21(=3×7)の素因数分解を行い記録を更新したが[85]、21を超える数の素因数分解に成功したという報告はない(2019年9月時点)。

量子コンピュータとしては、量子ゲート型以外に、D-Waveなどの量子アニーリングやその他いくつかのタイプが提案されている、量子イジングマシンはQUBO(制約のない二値二次式の最適化)(英語版)に特化した専用計算機と言える。
脚注[ソースを編集][脚注の使い方]
注釈[ソースを編集]^ 一般的でない例としては、数は少ないが3状態の素子で動作するコンピュータや、多値論理の応用などとして研究されている。MLC NANDフラッシュのように実用例も一部にはある。
^ ニューヨーク州ヨークタウンハイツの研究所に存在する。

出典[ソースを編集]^ a b IT用語辞典、量子コンピュータ[1]
^ a b c d [2]
^ Quantum Computing Companies: Ultimate List for 2022
^ “量子コンピュータの歴史?考案から実用化までの道のり?”. 株式会社ライトコード (2021年9月7日). 2024年4月13日閲覧。
^ Paul Benioff (1980年5月). “ ⇒The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines” (English). J. Stat. Phys.（英語版）. doi:10.1007/BF01011339. 2017年4月1日閲覧。
^ Richard Feynman , Peter W. Shor (1982年). “ ⇒Simulating Physics with Computers” (English). SIAMコンピュータジャーナル（英語版）. 2017年4月1日閲覧。
^ David Deutsch (1985年). “ ⇒Quantum theory, the Church-Turing principle and the universal quantum computer” (English). ペンシルベニア州立大学. 2017年4月1日閲覧。
^ Royal Society (1989年9月8日). “ ⇒Quantum computational networks”. JSTOR. 2017年4月1日閲覧。
^ Deutsch, David; Jozsa, Richard (1992年12月). “Rapid Solution of Problems by Quantum Computation” (English). Astrophysics Data System. doi:10.1098/rspa.1992.0167. 2017年4月1日閲覧。
^ Ethan Bernstein , Umesh Vazirani (1993年). “ ⇒Quantum complexity theory” (English). ペンシルベニア州立大学. doi:10.1.1.144.7852. 2017年4月1日閲覧。
^ a b ⇒Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", In Proceeding of 35th IEEE FOCS, pp.124-134, Santa Fe, NM, Nov 20-22, 1994. (ショアのアルゴリズムの論文)
^ Daniel R. Simon (1994年). “ ⇒On the Power of Quantum Computation”. ペンシルベニア州立大学. doi:10.1.1.51.5477. 2017年4月1日閲覧。
^ Andrew Steane (1996年5月13日). “ ⇒Multiple Particle Interference and Quantum Error Correction” (English). コーネル大学図書館（英語版）. コーネル大学. doi:10.1098 / rspa.1996.0136. 2017年4月1日閲覧。
^ A. R. Calderbank, Peter W. Shor (1996年4月16日). “ ⇒Good Quantum Error-Correcting Codes Exist” (English). コーネル大学図書館. コーネル大学. doi:10.1103/PhysRevA.54.1098. 2017年4月1日閲覧。
^ a b ⇒Lov K. Grover, "A fast quantum mechanical algorithm for database search", STOC'96, pp. 212?219, Philadelphia, Pennsylvania, United States, May 22-24, 1996. (グローバーのアルゴリズムの論文)
^ Serge Haroche, Jean-Michel Raimond & Michel Brune ; Le chat de Schrodinger se prete a l'experience - Voir en direct le passage du monde quantique au monde classique, La Recherche 301 (Septembre 1997) 50 (disponible ⇒en ligne)
^ Serge Haroche ; Une exploration au c?ur du monde quantique, dans : Qu'est-ce que l'Univers ?, Vol. 4 de l'Universite de Tous les Savoirs (sous la direction d'Yves Michaux), Odile Jacob (2001) 571.
^ Edward Farhi (MIT), Sam Gutmann (Northeastern) (1998年3月20日). “ ⇒Quantum Computation and Decision Trees” (English). コーネル大学図書館. コーネル大学. doi:10.1103/PhysRevA.58.915. 2017年4月1日閲覧。
^ Christopher R. Monroe en David J. Wineland. (2008年8月11日). “ ⇒Quantum Computing with Ions” (English). サイエンティフィック・アメリカン. 2017年4月1日閲覧。
^ a b c d e “ ⇒Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance”. 2016年6月17日閲覧。
^ a b ⇒Demonstration of Shor's quantum factoring algorithm using photonic qubits