量子コンピューティング において量子超越性 （りょうしちょうえつせい、英 : Quantum supremacy ）とは、プログラム可能な量子デバイスが、どの様な古典コンピュータでも実用的な時間では解決できない問題を解決できることを（問題の有用性に関係なく）証明することである[ 1] [ 2] 量子優位性 (quantum advantage) は、量子デバイスが古典コンピュータよりも速く問題を解決できることを表す。量子超越性には概念上、処理能力の高い量子コンピューターを構築するエンジニアリングタスクと、知られている最善の古典アルゴリズムに比べて、その量子コンピュータを用いて超多項式 (en:superpolynomial )の高速化ができるような問題を見つける計算複雑性理論上 のタスクが含まれる[ 3] [ 4] ユーリ・マニン （1980） [ 5] リチャード・ファインマン （1981）の量子計算の提案にさかのぼる[ 6]
量子優位性を実証する提案の例には、 アーロンソン(en:Scott Aaronson )とアルヒポフのボソンサンプリング提案[ 7] D-Wave の特殊なフラストレーテッドクラスターループ問題[ 8] 量子回路 の出力のサンプリングが含まれる[ 9]
素因数分解 と同様に、ランダム量子回路の出力分布をサンプリングすることは、合理的な複雑さの仮定に基づく古典的なコンピュータでは難しいと考えられている[ 9] Google は以前、49の超伝導量子ビットの配列でこの問題を解決することにより、2017年末までに量子優位性を実証する計画を発表した[ 10] [ 11] 量子ビット 数が増えた[ 12] NASA とのパートナーシップによって「Google量子プロセッサで実行される量子回路の結果を分析し、（中略）古典的なシミュレーションと比較して、ハードウェアの検証と量子超越性のベースラインの確立する。」と発表した[ 13] [ 14] [ 15] Financial Times は「Googleが54量子ビットのうち53量子ビットを使って、スーパーコンピュータが完了するのに約10,000年かかるタスクを200秒で実行し、量子超越性を達成したと主張している」と報じた[ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] 中国科学技術大学 はGoogleのような超伝導チップではなく、光子 を用いて潘建偉 の研究チームが開発した量子コンピュータ九章 が世界最速（当時）のスーパーコンピュータである富岳 では6億年かかるタスクを200秒で実行したと発表して中国 がアメリカ合衆国 に次いで量子超越性を達成した国となったと主張した[ 24] [ 25] [ 26] [ 27]
計算複雑性理論 は、問題を解決するために必要なリソース（通常は時間またはメモリ ）の量が、入力のサイズに対してどのように増加するかを論じる。 古典的な計算複雑性理論の 拡張として、 量子計算複雑性理論は、物理的な量子コンピュータの構築の難しさやデコヒーレンスとノイズの影響を必ずしも考慮せずに、理論的な汎用量子コンピュータに何ができるかを議論する[ 28] 量子情報 は古典的な情報を一般化したものであるため 、 量子コンピュータ はあらゆる古典的なアルゴリズムを シミュレートできる 。
複雑度クラスBQP （有界誤差量子多項式時間）は、 汎用量子コンピュータによって多項式時間 で解くことができる決定問題 のクラスである[ 29]
P
⊆
B
P
P
⊆
B
Q
P
⊆
P
S
P
A
C
E
{\displaystyle P\subseteq BPP\subseteq BQP\subseteq PSPACE}
^ Press. “Google touts quantum computing milestone ”. MarketWatch . 2020年8月21日 閲覧。 ^ “Demonstrating Quantum Supremacy ”. 2020年8月21日 閲覧。 ^ “Quantum Supremacy Using a Programmable Superconducting Processor ”. 2020年8月21日 閲覧。 ^ a b Arute, Frank (23 October 2019). “Quantum supremacy using a programmable superconducting processor”. Nature 574 (7779): 505–510. Bibcode : 2019Natur.574..505A . doi :10.1038/s41586-019-1666-5 .
PMID 31645734 .
^ “What the Google vs. IBM debate over quantum supremacy means | ZDNet ”. www.zdnet.com . 2020年8月21日 閲覧。 ^ “On "Quantum Supremacy" ”. IBM Research Blog (2019年10月22日). 2019年10月24日 閲覧。 ^ “Google Claims To Achieve Quantum Supremacy — IBM Pushes Back ”. NPR.org . 2019年10月24日 閲覧。 ^ “中国科技大、光量子コンピュータで「量子超越性」を実証 スパコン富岳で6億年かかる計算を200秒で” . ITmedia . https://www.itmedia.co.jp/news/articles/2012/04/news146.html 2020年12月9日 閲覧。 ^ “中国の量子コンピューター、世界最速スパコンで6億年要する計算を200秒で完了” . AFPBB . https://www.afpbb.com/articles/-/3319754 2020年12月9日 閲覧。 ^ “中国、世界最速スパコンの100兆倍速い量子コンピューター開発と主張” . ブルームバーグ . https://www.bloomberg.co.jp/news/articles/2020-12-04/QKSOMCDWLU6X01 2020年12月9日 閲覧。 ^ “中国の研究チームが達成した「量子超越性」が意味すること ”. WIRED 2020年12月9日 閲覧。 ^ Watrous, John (2009). “Quantum Computational Complexity” . In Meyers, Robert A.. Encyclopedia of Complexity and Systems Science . Springer New York. pp. 7174 –7201. doi :10.1007/978-0-387-30440-3_428 .
ISBN 9780387758886 . https://archive.org/details/encyclopediacomp00meye ^
Tereza, Tusarova (26 September 2004). "Quantum Complexity Classes". arXiv :cs/0409051 ^ Vazirani, Umesh. “A Survey of Quantum Complexity Theory” . Proceedings of Symposia in Applied Mathematics . https://www.csee.umbc.edu/~lomonaco/ams/lecturenotes/Vazirani.pdf . ^ Lund, A. P.; Bremner, Michael J.; Ralph, T. C. (2017-04-13). “Quantum sampling problems, BosonSampling and quantum supremacy”. NPJ Quantum Information 3 (1): 15. arXiv :1702.03061 . Bibcode : 2017npjQI...3...15L . doi :10.1038/s41534-017-0018-2 .
ISSN 2056-6387 . ^ Gard, Bryan T.; Motes, Keith R.; Olson, Jonathan P.; Rohde, Peter P.; Dowling, Jonathan P. (August 2015). “An introduction to boson-sampling”. From Atomic to Mesoscale: the Role of Quantum Coherence in Systems of Various Complexities . World Scientific. pp. 167–192. arXiv :1406.6767 . doi :10.1142/9789814678704_0008 .
ISBN 978-981-4678-70-4 ^ Bremner, Michael J.; Montanaro, Ashley; Shepherd, Dan J. (2016-08-18). “Average-case complexity versus approximate simulation of commuting quantum computations”. Physical Review Letters 117 (8): 080501. arXiv :1504.07999 . Bibcode : 2016PhRvL.117h0501B . doi :10.1103/PhysRevLett.117.080501 .
ISSN 0031-9007 .
PMID 27588839 . ^ Jordan. “Quantum Algorithm Zoo ”. math.nist.gov . 2018年4月29日時点のオリジナル よりアーカイブ。2017年7月29日 閲覧。 ^ a b Shor, P. (1999-01-01). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Review 41 (2): 303–332. arXiv :quant-ph/9508027 . Bibcode : 1999SIAMR..41..303S . doi :10.1137/S0036144598347011 .
ISSN 0036-1445 .
^
Rubinstein, Michael (19 October 2006). "The distribution of solutions to xy = N mod a with an application to factoring integers". arXiv :math/0610612 ^ Babai, László; Beals, Robert; Seress, Ákos (2009). Polynomial-time Theory of Matrix Groups . STOC '09. New York, NY, USA: ACM. 55–64. doi :10.1145/1536414.1536425 .
ISBN 9781605585062 ^ Rivest, R. L.; Shamir, A.; Adleman, L. (February 1978). “A Method for Obtaining Digital Signatures and Public-key Cryptosystems”. Commun. ACM 21 (2): 120–126. doi :10.1145/359340.359342 .
ISSN 0001-0782 . ^ Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (November 2012). “Experimental realization of Shor's quantum factoring algorithm using qubit recycling”. Nature Photonics 6 (11): 773–776. arXiv :1111.4147 . Bibcode : 2012NaPho...6..773M . doi :10.1038/nphoton.2012.259 .
ISSN 1749-4893 . ^ Fowler, Austin G.; Mariantoni, Matteo; Martinis, John M.; Cleland, Andrew N. (2012-09-18). “Surface codes: Towards practical large-scale quantum computation”. Physical Review A 86 (3): 032324. arXiv :1208.0928 . doi :10.1103/PhysRevA.86.032324 . ^ Rahimi-Keshari, Saleh; Ralph, Timothy C.; Caves, Carlton M. (2016-06-20). “Sufficient Conditions for Efficient Classical Simulation of Quantum Optics”. Physical Review X 6 (2): 021039. arXiv :1511.06526 . Bibcode : 2016PhRvX...6b1039R . doi :10.1103/PhysRevX.6.021039 . ^ Carolan, Jacques; Harrold, Christopher; Sparrow, Chris; Martín-López, Enrique; Russell, Nicholas J.; Silverstone, Joshua W.; Shadbolt, Peter J.; Matsuda, Nobuyuki et al. (2015-08-14). “Universal linear optics”. Science 349 (6249): 711–716. arXiv :1505.01182 . doi :10.1126/science.aab3642 .
ISSN 0036-8075 .
PMID 26160375 . ^
Clifford, Peter; Clifford, Raphaël (5 June 2017). "The Classical Complexity of Boson Sampling". arXiv :1706.01260 cs.DS ]。 ^ Neville, Alex; Sparrow, Chris; Clifford, Raphaël; Johnston, Eric; Birchall, Patrick M.; Montanaro, Ashley; Laing, Anthony (2017-10-02). “No imminent quantum supremacy by boson sampling”. Nature Physics 13 (12): 1153–1157. arXiv :1705.00686 . Bibcode : 2017arXiv170500686N . doi :10.1038/nphys4270 .
ISSN 1745-2473 . ^ Hans De Raedt; Fengping Jin; Dennis Willsch; Madita Willsch; Naoki Yoshioka; Nobuyasu Ito; Shengjun Yuan; Kristel Michielsen (November 2018). “Massively parallel quantum computer simulator, eleven years later”. Computer Physics Communications 237 : 47-61. doi :10.1016/j.cpc.2018.11.005 . ^
Edwin Pednault; John A. Gunnels (October 2017). "Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits". arXiv :1710.05867 quant-ph ]。 ^ “Quantum Supremacy Using a Programmable Superconducting Processor ”. Google AI Blog . 2019年11月2日 閲覧。 ^ Metz, Cade (23 October 2019). “Google Claims a Quantum Breakthrough That Could Change Computing” . The New York Times . https://www.nytimes.com/2019/10/23/technology/quantum-computing-google.html 14 January 2020 閲覧。 ^
Kalai, Gil (2 June 2011). "How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation". arXiv :1106.0485 quant-ph ]。 ^ Shor, Peter W. (1995-10-01). “Scheme for reducing decoherence in quantum computer memory”. Physical Review A 52 (4): R2493–R2496. Bibcode : 1995PhRvA..52.2493S . doi :10.1103/PhysRevA.52.R2493 .
PMID 9912632 . ^ Steane, A. M. (1996-07-29). “Error Correcting Codes in Quantum Theory”. Physical Review Letters 77 (5): 793–797. Bibcode : 1996PhRvL..77..793S . doi :10.1103/PhysRevLett.77.793 .
PMID 10062908 . ^
Aharonov, Dorit; Ben-Or, Michael (30 June 1999). "Fault-Tolerant Quantum Computation With Constant Error Rate". arXiv :quant-ph/9906129 ^ Knill, E. (2005-03-03). “Quantum computing with realistically noisy devices”. Nature 434 (7029): 39–44. arXiv :quant-ph/0410199 . Bibcode : 2005Natur.434...39K . doi :10.1038/nature03350 .
ISSN 0028-0836 .
PMID 15744292 . ^
Kalai, Gil (3 May 2016). "The Quantum Computer Puzzle (Expanded Version)". arXiv :1605.00992 quant-ph ]。 ^ Dyakonov, M. I. (2007). “Is Fault-Tolerant Quantum Computation Really Possible?”. In S. Luryi. Future Trends in Microelectronics. Up the Nano Creek . Wiley. pp. 4–18. arXiv :quant-ph/0610117 . Bibcode : 2006quant.ph.10117D ^ Tang, Ewin (2019-05-09). “A quantum-inspired classical algorithm for recommendation systems”. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 . pp. 217–228. arXiv :1807.04271v3 . doi :10.1145/3313276.3316310 .
ISBN 9781450367059 ^ Palacios-Berraquero, Carmen; Mueck, Leonie; Persaud, Divya M. (2019-12-10). “Instead of 'supremacy' use 'quantum advantage'” (英語). Nature 576 (7786): 213. doi :10.1038/d41586-019-03781-0 .
PMID 31822842 . ^ Board. “Opinion | Achieving Quantum Wokeness ” (英語). WSJ . 2019年12月21日 閲覧。 ^ Knapton, Sarah (2019年12月17日). “Academics derided for claiming 'quantum supremacy' is a racist and colonialist term” (英語). The Telegraph .
ISSN 0307-1235 . https://www.telegraph.co.uk/science/2019/12/17/academics-derided-claiming-quantum-supremacy-racist-colonialist/ 2019年12月21日 閲覧。 ^ “John Preskill Explains ‘Quantum Supremacy’ ” (英語). Quanta Magazine . 2020年4月21日 閲覧。 ^ “John Preskill Explains ‘Quantum Supremacy’ ” (英語). Quanta Magazine . 2020年4月21日 閲覧。 ^ Martinis. “Quantum Supremacy Using a Programmable Superconducting Processor ” (英語). Google AI Blog . Alphabet. 5 December 2019 閲覧。
全般
ハードウェア
アルゴリズム•
項目
関連分野
メーカー
実機
人物
カテゴリ
要購読契約) 
全ての辞書から量子超越性
を検索
