量子超越性とは？わかりやすく解説

量子コンピューティングにおいて量子超越性（りょうしちょうえつせい、英: 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]。2018年1月初旬、インテルは同様のハードウェアプログラムを発表した^[11]。2017年10月、IBMが従来のスーパーコンピューターで56量子ビットのシミュレーションを実演したことにより、量子優位性に必要な量子ビット数が増えた^[12]。2018年11月、GoogleはNASAとのパートナーシップによって「Google量子プロセッサで実行される量子回路の結果を分析し、（中略）古典的なシミュレーションと比較して、ハードウェアの検証と量子超越性のベースラインの確立する。」と発表した^[13]。2018年に発表された理論的な研究によると、エラー率を十分低くすることができれば、「7x7の2次元格子の量子ビットと約40クロックサイクル」で量子優位性が実現することが示唆された^[14]。2019年6月18日、Quanta Magazineは、Nevenの法則に従って、量子超越性が2019年に実現する可能性があることを示唆した^[15]。2019年9月20日、Financial Timesは「Googleが54量子ビットのうち53量子ビットを使って、スーパーコンピュータが完了するのに約10,000年かかるタスクを200秒で実行し、量子超越性を達成したと主張している」と報じた^[16]^[17]。10月23日、Googleはこの主張を主張していることを正式に認めた^[18]^[19]^[20]。IBMは、10,000年ではなく2.5日で実行可能であって、一部の主張は過剰であると反論した^[21]^[22]^[23]。2020年12月3日、中国科学技術大学はGoogleのような超伝導チップではなく、光子を用いて潘建偉の研究チームが開発した量子コンピュータ九章が世界最速（当時）のスーパーコンピュータである富岳では6億年かかるタスクを200秒で実行したと発表して中国がアメリカ合衆国に次いで量子超越性を達成した国となったと主張した^[24]^[25]^[26]^[27]。

計算の複雑さ

計算複雑性理論は、問題を解決するために必要なリソース（通常は時間またはメモリ）の量が、入力のサイズに対してどのように増加するかを論じる。古典的な計算複雑性理論の拡張として、量子計算複雑性理論は、物理的な量子コンピュータの構築の難しさやデコヒーレンスとノイズの影響を必ずしも考慮せずに、理論的な汎用量子コンピュータに何ができるかを議論する^[28]。量子情報は古典的な情報を一般化したものであるため、量子コンピュータはあらゆる古典的なアルゴリズムをシミュレートできる。

複雑度クラスBQP （有界誤差量子多項式時間）は、汎用量子コンピュータによって多項式時間で解くことができる決定問題のクラスである^[29]。重要な古典的複雑性クラスの階層に関連付けらる $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. (2020年12月4日) 2020年12月9日閲覧。

^ “中国の量子コンピューター、世界最速スパコンで6億年要する計算を200秒で完了”. AFPBB. (2020年12月8日) 2020年12月9日閲覧。

^ “中国、世界最速スパコンの100兆倍速い量子コンピューター開発と主張”. ブルームバーグ. (2020年12月4日) 2020年12月9日閲覧。

^ “中国の研究チームが達成した「量子超越性」が意味すること”. WIRED (2020年12月5日). 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

^ 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.

^ 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 (2019年10月23日). “Google Claims a Quantum Breakthrough That Could Change Computing”. The New York Times 2020年1月14日閲覧。

^ 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 2019年12月21日閲覧。

^ “John Preskill Explains ‘Quantum Supremacy’” (英語). Quanta Magazine. 2020年4月21日閲覧。

^ Martinis. “Quantum Supremacy Using a Programmable Superconducting Processor” (英語). Google AI Blog. Alphabet. 2019年12月5日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

表話編歴量子コンピュータ
全般	量子コンピュータ量子力学
ハードウェア	超伝導イオントラップ型核磁気共鳴光子
アルゴリズム• プログラミング言語	量子プログラミング言語ドイッチュ・ジョサのアルゴリズムグローバーのアルゴリズムショアのアルゴリズム（英語版）
項目	量子ビット量子回路量子テレポーテーション量子暗号量子アニーリング量子状態量子もつれ量子超越性量子ウォーク量子情報
関連分野	量子情報科学情報工学
メーカー	IBM D-Wave Google
実機	九章
人物	ピーター・ショアロブ・グローバー（英語版）デイヴィッド・ドイッチュリチャード・ジョサ（英語版）
カテゴリ

量子超越性とは？わかりやすく解説

りょうし‐ちょうえつせい〔リヤウシテウヱツセイ〕【量子超越性】