量子超越性のソースを表示

[[量子コンピューティング]]において'''量子超越性'''（りょうしちょうえつせい、{{lang-en-short|Quantum supremacy}}）とは、プログラム可能な量子デバイスが、どの様な古典コンピュータでも実用的な時間では解決できない問題を解決できることを（問題の有用性に関係なく）証明することである<ref name=":0">{{Cite arXiv|arxiv=1203.5813|class=quant-ph|last=Preskill|first=John|title=Quantum computing and the entanglement frontier|date=2012-03-26}}</ref><ref name=":12">{{Cite journal|last=Preskill|first=John|date=2018-08-06|title=Quantum Computing in the NISQ era and beyond|journal=Quantum|volume=2|pages=79|DOI=10.22331/q-2018-08-06-79}}</ref>。それよりも弱い'''量子優位性''' (quantum advantage) は、量子デバイスが古典コンピュータよりも速く問題を解決できることを表す。量子超越性には概念上、処理能力の高い量子コンピューターを構築するエンジニアリングタスクと、知られている最善の古典アルゴリズムに比べて、その量子コンピュータを用いて超多項式 ([[:en:superpolynomial]])の高速化ができるような問題を見つける[[計算複雑性理論|計算複雑性理論上]]のタスクが含まれる<ref name=":13">{{Cite journal|last=Harrow|first=Aram W.|last2=Montanaro|first2=Ashley|date=September 2017|title=Quantum computational supremacy|journal=Nature|volume=549|issue=7671|pages=203–209|arxiv=1809.07442|DOI=10.1038/nature23458|ISSN=1476-4687|PMID=28905912}}</ref><ref>{{Cite journal|last=Papageorgiou|first=Anargyros|last2=Traub|first2=Joseph F.|date=2013-08-12|title=Measures of quantum computing speedup|journal=Physical Review A|volume=88|issue=2|pages=022316|arxiv=1307.7488|bibcode=2013PhRvA..88b2316P|DOI=10.1103/PhysRevA.88.022316|ISSN=1050-2947}}</ref>。この用語は元々[[ジョン・プレスキル]]によって広められたが、量子コンピューティングの利点、特に量子システムのシミュレーションの概念は、 [[ユーリ・マニン]] （1980） <ref name="manin1980vychislimoe">{{Cite book|last=Manin, Yu. I.|title=Vychislimoe i nevychislimoe|trans-title=Computable and Noncomputable|year=1980|publisher=Sov.Radio|url=http://publ.lib.ru/ARCHIVES/M/MANIN_Yuriy_Ivanovich/Manin_Yu.I._Vychislimoe_i_nevychislimoe.(1980).%5Bdjv%5D.zip|pages=13–15|language=Russian|accessdate=2013-03-04|archiveurl=https://web.archive.org/web/20130510173823/http://publ.lib.ru/ARCHIVES/M/MANIN_Yuriy_Ivanovich/Manin_Yu.I._Vychislimoe_i_nevychislimoe.(1980).%5Bdjv%5D.zip|archivedate=2013-05-10}}
</ref>および[[リチャード・P・ファインマン|リチャード・ファインマン]] （1981）の量子計算の提案にさかのぼる<ref>{{Cite journal|last=Feynman|first=Richard P.|date=1982-06-01|title=Simulating Physics with Computers|journal=International Journal of Theoretical Physics|volume=21|issue=6–7|pages=467–488|bibcode=1982IJTP...21..467F|DOI=10.1007/BF02650179|ISSN=0020-7748}}</ref>。

量子優位性を実証する提案の例には、 アーロンソン([[:en:Scott Aaronson]])とアルヒポフのボソンサンプリング提案<ref name=":3">{{Cite book|last=Aaronson|first=Scott|last2=Arkhipov|first2=Alex|date=2011|title=The Computational Complexity of Linear Optics|journal=Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing|series=STOC '11|location=New York, NY, USA|publisher=ACM|pages=333–342|doi=10.1145/1993636.1993682|isbn=9781450306911|arxiv=1011.3245}}</ref>、[[D-Wave Systems|D-Wave]]の特殊なフラストレーテッドクラスターループ問題<ref>{{Cite arXiv|arxiv=1701.04579|class=quant-ph|last=King|first=James|last2=Yarkoni|first2=Sheir|title=Quantum Annealing amid Local Ruggedness and Global Frustration|date=2017-01-17}}</ref>とランダム[[量子回路]]の出力のサンプリングが含まれる<ref name=":1">{{Cite arXiv|arxiv=1612.05903|class=quant-ph|last=Aaronson|first=Scott|last2=Chen|first2=Lijie|title=Complexity-Theoretic Foundations of Quantum Supremacy Experiments|date=2016-12-18}}</ref>。

[[素因数分解]]と同様に、ランダム量子回路の出力分布をサンプリングすることは、合理的な複雑さの仮定に基づく古典的なコンピュータでは難しいと考えられている<ref name=":1">{{Cite arXiv|arxiv=1612.05903|class=quant-ph|last=Aaronson|first=Scott|last2=Chen|first2=Lijie|title=Complexity-Theoretic Foundations of Quantum Supremacy Experiments|date=2016-12-18}}</ref>。[[Google]]は以前、49の[[超伝導量子ビット]]の配列でこの問題を解決することにより、2017年末までに量子優位性を実証する計画を発表した<ref name=":9">{{Cite news|url=https://spectrum.ieee.org/computing/hardware/google-plans-to-demonstrate-the-supremacy-of-quantum-computing|title=Google Plans to Demonstrate the Supremacy of Quantum Computing|newspaper=IEEE Spectrum: Technology, Engineering, and Science News|accessdate=2018-01-11}}</ref>。2018年1月初旬、インテルは同様のハードウェアプログラムを発表した<ref name=":11">{{Cite news|url=https://spectrum.ieee.org/tech-talk/computing/hardware/intels-49qubit-chip-aims-for-quantum-supremacy|title=CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy|newspaper=IEEE Spectrum: Technology, Engineering, and Science News|accessdate=2017-07-22}}</ref>。2017年10月、IBMが従来のスーパーコンピューターで56量子ビットのシミュレーションを実演したことにより、量子優位性に必要な[[量子ビット]]数が増えた<ref name=":8">{{Cite web|url=https://www.newscientist.com/article/2151032-googles-quantum-computing-plans-threatened-by-ibm-curveball/|title=Google's quantum computing plans threatened by IBM curveball|date=October 20, 2017|accessdate=October 22, 2017}}</ref>。2018年11月、Googleは[[アメリカ航空宇宙局|NASA]]とのパートナーシップによって「Google量子プロセッサで実行される量子回路の結果を分析し、（中略）古典的なシミュレーションと比較して、ハードウェアの検証と量子超越性のベースラインの確立する。」と発表した<ref>{{Cite news|url=https://www.technologyreview.com/s/612381/google-has-enlisted-nasa-to-help-it-prove-quantum-supremacy-within-months/|title=Google has enlisted NASA to help it prove quantum supremacy within months|last=Harris|first=Mark|newspaper=MIT Technology Review|accessdate=2018-11-30}}</ref>。2018年に発表された理論的な研究によると、エラー率を十分低くすることができれば、「7x7の2次元格子の量子ビットと約40クロックサイクル」で量子優位性が実現することが示唆された<ref name="Boixo">{{Cite journal|last=Boixo|first=Sergio|last2=Isakov|first2=Sergei V.|last3=Smelyanskiy|first3=Vadim N.|last4=Babbush|first4=Ryan|last5=Ding|first5=Nan|last6=Jiang|first6=Zhang|last7=Bremner|first7=Michael J.|last8=Martinis|first8=John M.|last9=Neven|first9=Hartmut|date=23 April 2018|title=Characterizing quantum supremacy in near-term devices|journal=Nature Physics|volume=14|issue=6|pages=595–600|arxiv=1608.00263|DOI=10.1038/s41567-018-0124-x}}</ref>。2019年6月18日、Quanta Magazineは、Nevenの法則に従って、量子超越性が2019年に実現する可能性があることを示唆した<ref>{{Cite web|url=https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/|title=A New Law to Describe Quantum Computing's Rise?|website=[[Quanta Magazine]]|date=June 18, 2019|author=Hartnett|first=Kevin|accessdate=2020/08/21|publisher=}}</ref>。2019年9月20日、[[フィナンシャル・タイムズ|Financial Times]]は「Googleが54量子ビットのうち53量子ビットを使って、スーパーコンピュータが完了するのに約10,000年かかるタスクを200秒で実行し、量子超越性を達成したと主張している」と報じた<ref>[https://www.ft.com/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17], ''[[フィナンシャル・タイムズ|Financial Times]]'', September 2019 {{Subscription required}}</ref><ref>{{Cite web|url=https://www.marketwatch.com/story/google-touts-quantum-computing-milestone-2019-10-23|title=Google touts quantum computing milestone|first=Associated|author=Press|website=MarketWatch|accessdate=2020/08/21|publisher=}}</ref>。10月23日、Googleはこの主張を主張していることを正式に認めた<ref>{{Cite web|url=https://www.youtube.com/watch?v=-ZNEzzDcllU|title=Demonstrating Quantum Supremacy|accessdate=2020/08/21|publisher=}}</ref><ref>{{Cite web|url=https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html|title=Quantum Supremacy Using a Programmable Superconducting Processor|accessdate=2020/08/21|publisher=}}</ref><ref name="NAT-20191023">{{Cite journal|last=Arute, Frank|date=23 October 2019|title=Quantum supremacy using a programmable superconducting processor|journal=[[Nature (journal)|Nature]]|volume=574|issue=7779|pages=505–510|bibcode=2019Natur.574..505A|DOI=10.1038/s41586-019-1666-5|PMID=31645734}}</ref>。IBMは、10,000年ではなく2.5日で実行可能であって、一部の主張は過剰であると反論した<ref>{{Cite web|url=https://www.zdnet.com/google-amp/article/what-the-google-v-ibm-debate-over-quantum-means/|title=What the Google vs. IBM debate over quantum supremacy means &#124; ZDNet|website=www.zdnet.com|accessdate=2020/08/21|publisher=}}</ref><ref>{{Cite web|url=https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/|title=On "Quantum Supremacy"|date=2019-10-22|website=IBM Research Blog|accessdate=2019-10-24}}</ref><ref>{{Cite web|url=https://www.npr.org/2019/10/23/772710977/google-claims-to-achieve-quantum-supremacy-ibm-pushes-back|title=Google Claims To Achieve Quantum Supremacy — IBM Pushes Back|website=NPR.org|accessdate=2019-10-24}}</ref>。2020年12月3日、[[中国科学技術大学]]はGoogleのような超伝導チップではなく、[[光子]]を用いて[[潘建偉]]の研究チームが開発した量子コンピュータ[[:zh:九章 (量子计算机)|九章]]が世界最速（当時）のスーパーコンピュータである[[富岳 (スーパーコンピュータ)|富岳]]では6億年かかるタスクを200秒で実行したと発表して[[中華人民共和国|中国]]が[[アメリカ合衆国]]に次いで量子超越性を達成した国となったと主張した<ref>{{Cite news|url=https://www.itmedia.co.jp/news/articles/2012/04/news146.html|title=中国科技大、光量子コンピュータで「量子超越性」を実証　スパコン富岳で6億年かかる計算を200秒で|newspaper=[[ITmedia]]|date=2020-12-04|accessdate=2020-12-09}}</ref><ref>{{Cite news|url=https://www.afpbb.com/articles/-/3319754|title=中国の量子コンピューター、世界最速スパコンで6億年要する計算を200秒で完了|newspaper=[[AFPBB]]|date=2020-12-08|accessdate=2020-12-09}}</ref><ref>{{Cite news|url=https://www.bloomberg.co.jp/news/articles/2020-12-04/QKSOMCDWLU6X01|title=中国、世界最速スパコンの100兆倍速い量子コンピューター開発と主張|newspaper=[[ブルームバーグ (企業)|ブルームバーグ]]|date=2020-12-04|accessdate=2020-12-09}}</ref><ref>{{Cite web|和書|url=https://wired.jp/2020/12/05/china-stakes-claim-quantum-supremacy/|title=中国の研究チームが達成した「量子超越性」が意味すること|date=2020-12-05|website=[[WIRED]]|accessdate=2020-12-09}}</ref>。

== 計算の複雑さ ==
[[計算複雑性理論]]は、問題を解決するために必要なリソース（通常は時間またはメモリ ）の量が、入力のサイズに対してどのように増加するかを論じる。 古典的な[[計算複雑性理論|計算複雑性理論の]]拡張として、 [[量子計算複雑性理論]]は、物理的な量子コンピュータの構築の難しさやデコヒーレンスとノイズの影響を必ずしも考慮せずに、理論的な[[量子チューリングマシン|汎用量子コンピュータ]]に何ができるかを議論する<ref name=":5">{{Cite book|title=Encyclopedia of Complexity and Systems Science|url=https://archive.org/details/encyclopediacomp00meye|last=Watrous|first=John|date=2009|publisher=Springer New York|isbn=9780387758886|editor-last=Meyers|editor-first=Robert A.|pages=[https://archive.org/details/encyclopediacomp00meye/page/n3382 7174]–7201|doi=10.1007/978-0-387-30440-3_428|chapter=Quantum Computational Complexity}}</ref>。[[量子情報]]は古典的な情報を一般化したものであるため 、 [[量子コンピュータ]]はあらゆる[[アルゴリズム|古典的なアルゴリズムを]]シミュレートできる 。 

複雑度クラス[[BQP]] （有界誤差量子多項式時間）は、 汎用量子コンピュータによって[[計算複雑性理論|多項式時間]]で解くことができる[[決定問題]]のクラスである<ref>{{Cite arXiv|arxiv=cs/0409051|last=Tereza|first=Tusarova|title=Quantum Complexity Classes|date=2004-09-26}}</ref>。重要な古典的複雑性クラスの階層に関連付けらる<math>P\subseteq BPP\subseteq BQP\subseteq PSPACE</math><ref name=":6">{{Cite journal|last=Vazirani|first=Umesh|title=A Survey of Quantum Complexity Theory|url=https://www.csee.umbc.edu/~lomonaco/ams/lecturenotes/Vazirani.pdf|journal=Proceedings of Symposia in Applied Mathematics}}</ref>。これらの包含関係が厳密かどうか（等号が成立しないかどうか）はどれも未解決の問題である。 

古典的なコンピューティングでは計算できないことを証明する難しさは、量子優越性を示す上での一般的な課題である。 白黒をはっきりつける決定問題とは異なり、サンプリング問題は、ある[[確率分布]]からのサンプルを求める。<ref name=":7">{{Cite journal|last=Lund|first=A. P.|last2=Bremner|first2=Michael J.|last3=Ralph|first3=T. C.|date=2017-04-13|title=Quantum sampling problems, BosonSampling and quantum supremacy|journal=NPJ Quantum Information|volume=3|issue=1|page=15|arxiv=1702.03061|bibcode=2017npjQI...3...15L|DOI=10.1038/s41534-017-0018-2|ISSN=2056-6387}}</ref> 任意の[[量子回路]]の出力から効率的にサンプリングできる[[アルゴリズム|古典的なアルゴリズム]]がある場合、 [[多項式階層]]は第3レベルに折りたたまれるが、これはほとんどあり得ないと考えられてる。<ref name=":1">{{Cite arXiv|arxiv=1612.05903|class=quant-ph|last=Aaronson|first=Scott|last2=Chen|first2=Lijie|title=Complexity-Theoretic Foundations of Quantum Supremacy Experiments|date=2016-12-18}}</ref> [[ボソンサンプリング]]は、より具体的な提案であり、その古典的な難しさは、複雑なエントリを持つ大きな行列の[[パーマネント (数学)|パーマネント]]を計算する難しさに依存する。これは、#P完全な問題である<ref>{{Cite book|last=Gard|date=August 2015|pages=167–192|arxiv=1406.6767|isbn=978-981-4678-70-4|publisher=World Scientific|title=From Atomic to Mesoscale: the Role of Quantum Coherence in Systems of Various Complexities|chapter=An introduction to boson-sampling|first5=Jonathan P.|first=Bryan T.|last5=Dowling|first4=Peter P.|last4=Rohde|first3=Jonathan P.|last3=Olson|first2=Keith R.|last2=Motes|doi=10.1142/9789814678704_0008}}</ref>。この結論に到達するために使用された議論は、IQPサンプリング<ref>{{Cite journal|last=Bremner|first=Michael J.|last2=Montanaro|first2=Ashley|last3=Shepherd|first3=Dan J.|date=2016-08-18|title=Average-case complexity versus approximate simulation of commuting quantum computations|journal=Physical Review Letters|volume=117|issue=8|page=080501|arxiv=1504.07999|bibcode=2016PhRvL.117h0501B|DOI=10.1103/PhysRevLett.117.080501|ISSN=0031-9007|PMID=27588839}}</ref>にも拡張され、そこでは問題の平均と最悪のケースの複雑さは同じであるという推測のみが必要となる。 

== 提案された実験 ==
以下は、現在[[NISQ]]デバイスと呼ばれることが多い現在の技術を使用して、量子計算の優位性を実証するための提案である<ref name=":12">{{Cite journal|last=Preskill|first=John|date=2018-08-06|title=Quantum Computing in the NISQ era and beyond|journal=Quantum|volume=2|pages=79|DOI=10.22331/q-2018-08-06-79}}</ref>。そのような提案には、（1）明確に定義された計算上の問題、（2）その問題を解決するための[[量子アルゴリズム]] 、（3）最善の古典アルゴリズムとの比較、および（4）合理的な仮定の下では、現在存在する古典アルゴリズムが大幅に改善する見込みがないと言う計算複雑性理論上の議論、が含まれる（そのため、量子アルゴリズムはあらゆる古典アルゴリズムに対して超多項式の高速化を提供する）<ref name=":13">{{Cite journal|last=Harrow|first=Aram W.|last2=Montanaro|first2=Ashley|date=September 2017|title=Quantum computational supremacy|journal=Nature|volume=549|issue=7671|pages=203–209|arxiv=1809.07442|DOI=10.1038/nature23458|ISSN=1476-4687|PMID=28905912}}</ref><ref>{{Cite web|url=http://math.nist.gov/quantum/zoo/|title=Quantum Algorithm Zoo|author=Jordan|first=Stephen|website=math.nist.gov|accessdate=2017-07-29|archiveurl=https://web.archive.org/web/20180429014516/https://math.nist.gov/quantum/zoo/|archivedate=2018-04-29}}</ref>。 

=== ショアのアルゴリズム ===
[[:en:Shor's algorithm|ショアのアルゴリズム]]は、 ''n''ビット整数の素因数分解を<math>\tilde{O} (n^3)</math>時間で行う<ref name=":2">{{Cite journal|last=Shor|first=P.|date=1999-01-01|title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer|journal=SIAM Review|volume=41|issue=2|pages=303–332|arxiv=quant-ph/9508027|bibcode=1999SIAMR..41..303S|DOI=10.1137/S0036144598347011|ISSN=0036-1445}}</ref>。これに対して、知られている最善の古典アルゴリズムは<math>2^{O(n^{1/3})}</math>時間必要である。また、この問題の複雑さの最良の上界は<math>O(2^{n/3+o(1)})</math> である<ref>{{Cite arXiv|arxiv=math/0610612|last=Rubinstein|first=Michael|title=The distribution of solutions to xy = N mod a with an application to factoring integers|date=2006-10-19}}</ref>。このアルゴリズムは[[素因数分解|整数因数分解]]に帰着される全ての問題を高速化する。その中には奇数オーダーの[[可換体]]上の[[行列群]]のメンバーシップ問題が含まれる<ref>{{Cite book|last=Babai|first=László|last2=Beals|first2=Robert|last3=Seress|first3=Ákos|date=2009|title=Polynomial-time Theory of Matrix Groups|journal=Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing|series=STOC '09|location=New York, NY, USA|publisher=ACM|pages=55–64|doi=10.1145/1536414.1536425|isbn=9781605585062}}</ref>。 

この[[アルゴリズム]]は、 [[量子コンピュータ|量子コンピューティング]]にとって実用的にも歴史的にも重要である。古典コンピュータでは解くことの出来ないと信じられている現実の問題に対して提案された、最初の多項式時間量子アルゴリズムである<ref name=":2">{{Cite journal|last=Shor|first=P.|date=1999-01-01|title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer|journal=SIAM Review|volume=41|issue=2|pages=303–332|arxiv=quant-ph/9508027|bibcode=1999SIAMR..41..303S|DOI=10.1137/S0036144598347011|ISSN=0036-1445}}</ref>。つまり、今日合理的に信じられている暗号化プロトコルである[[RSA暗号|RSA]]が安全であるという仮定の下で、このアルゴリズムは超多項式の高速化を実現する<ref>{{Cite journal|last=Rivest|first=R. L.|last2=Shamir|first2=A.|last3=Adleman|first3=L.|date=February 1978|title=A Method for Obtaining Digital Signatures and Public-key Cryptosystems|journal=Commun. ACM|volume=21|issue=2|pages=120–126|DOI=10.1145/359340.359342|ISSN=0001-0782}}</ref>。 

例え非常に大きな数の場合でも、因数分解は乗算するだけで従来のコンピューターですばやくチェックできるため、因数分解は他の量子優位性の提案よりも利点がある。ただし、Shorのアルゴリズムを大きな数に対して実装することは、現在の技術では不可能なため<ref>{{Cite journal|last=Martín-López|first=Enrique|last2=Laing|first2=Anthony|last3=Lawson|first3=Thomas|last4=Alvarez|first4=Roberto|last5=Zhou|first5=Xiao-Qi|last6=O'Brien|first6=Jeremy L.|date=November 2012|title=Experimental realization of Shor's quantum factoring algorithm using qubit recycling|journal=Nature Photonics|volume=6|issue=11|pages=773–776|arxiv=1111.4147|bibcode=2012NaPho...6..773M|DOI=10.1038/nphoton.2012.259|ISSN=1749-4893}}</ref><ref>{{Cite journal|last=Fowler|first=Austin G.|last2=Mariantoni|first2=Matteo|last3=Martinis|first3=John M.|last4=Cleland|first4=Andrew N.|date=2012-09-18|title=Surface codes: Towards practical large-scale quantum computation|journal=Physical Review A|volume=86|issue=3|pages=032324|arxiv=1208.0928|DOI=10.1103/PhysRevA.86.032324}}</ref>、優位性を実証するための戦略として追求されていない。 

=== ボソンサンプリング ===
[[線形光学ネットワーク]]を介して送信された同一の[[光子|光子に]]基づくこの計算パラダイムは、古典アルゴリズムが(ガウス行列の[[パーマネント (数学)|パーマネント]]の計算が[[＃P|#P-Hard]]であり、 [[多項式階層]]が潰れないと言う、計算複雑性理論上の予想の下で）解くことが出来ない、特定のサンプリング及び検索問題を解くことができる<ref name=":3">{{Cite book|last=Aaronson|first=Scott|last2=Arkhipov|first2=Alex|date=2011|title=The Computational Complexity of Linear Optics|journal=Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing|series=STOC '11|location=New York, NY, USA|publisher=ACM|pages=333–342|doi=10.1145/1993636.1993682|isbn=9781450306911|arxiv=1011.3245}}</ref>。ただし、十分に大きな損失とノイズがあるシステムでのボソンサンプリングは、効率的にシミュレーションできることが示されている<ref>{{Cite journal|last=Rahimi-Keshari|first=Saleh|last2=Ralph|first2=Timothy C.|last3=Caves|first3=Carlton M.|date=2016-06-20|title=Sufficient Conditions for Efficient Classical Simulation of Quantum Optics|journal=Physical Review X|volume=6|issue=2|pages=021039|arxiv=1511.06526|bibcode=2016PhRvX...6b1039R|DOI=10.1103/PhysRevX.6.021039}}</ref>。 

これまでのボソンサンプリングの最大の実験では、6つのモードがあり、一度に最大6つの光子を処理できた<ref>{{Cite journal|last=Carolan|first=Jacques|last2=Harrold|first2=Christopher|last3=Sparrow|first3=Chris|last4=Martín-López|first4=Enrique|last5=Russell|first5=Nicholas J.|last6=Silverstone|first6=Joshua W.|last7=Shadbolt|first7=Peter J.|last8=Matsuda|first8=Nobuyuki|last9=Oguma|first9=Manabu|date=2015-08-14|title=Universal linear optics|journal=Science|volume=349|issue=6249|pages=711–716|arxiv=1505.01182|DOI=10.1126/science.aab3642|ISSN=0036-8075|PMID=26160375}}</ref>。時間内にボソンサンプリングの実行をシミュレート[[アルゴリズム|する]]ための最善の古典[[アルゴリズム]]は、''n個の'' [[光子]]と''m個の''出力モードを持つシステムの''場合、'' <math>O(n2^n+mn^2)</math> 時間で動作する<ref name=":10">{{Cite arXiv|arxiv=1706.01260|class=cs.DS|last=Clifford|first=Peter|last2=Clifford|first2=Raphaël|title=The Classical Complexity of Boson Sampling|date=2017-06-05}}</ref><ref name=":4">{{Cite journal|last=Neville|first=Alex|last2=Sparrow|first2=Chris|last3=Clifford|first3=Raphaël|last4=Johnston|first4=Eric|last5=Birchall|first5=Patrick M.|last6=Montanaro|first6=Ashley|last7=Laing|first7=Anthony|date=2017-10-02|title=No imminent quantum supremacy by boson sampling|journal=Nature Physics|volume=13|issue=12|pages=1153–1157|arxiv=1705.00686|bibcode=2017arXiv170500686N|DOI=10.1038/nphys4270|ISSN=1745-2473}}</ref>。[https://CRAN.R-project.org/package=BosonSampling BosonSampling]は[[R言語|R]]でのオープンソース実装である。このアルゴリズムによると、ボソンサンプリングで量子優位性を実証するためには、50個の[[光子]]が必要であると推定される。


=== ランダム量子回路の出力分布のサンプリング ===
任意のランダム[[量子回路]]をシミュレートするための最善の[[アルゴリズム]]の実行時間は、 [[量子ビット]]数に応じて指数関数的に増加する。あるグループは、およそ50[[量子ビット]]があれば量子超越性を実証するのに十分であると推定した<ref name="Boixo">{{Cite journal|last=Boixo|first=Sergio|last2=Isakov|first2=Sergei V.|last3=Smelyanskiy|first3=Vadim N.|last4=Babbush|first4=Ryan|last5=Ding|first5=Nan|last6=Jiang|first6=Zhang|last7=Bremner|first7=Michael J.|last8=Martinis|first8=John M.|last9=Neven|first9=Hartmut|date=23 April 2018|title=Characterizing quantum supremacy in near-term devices|journal=Nature Physics|volume=14|issue=6|pages=595–600|arxiv=1608.00263|DOI=10.1038/s41567-018-0124-x}}</ref>。[[Google]]は、49 [[量子ビット]]チップを構築して、現在の古典的なコンピューターが妥当な時間内にアクセスできない確率分布を作ることにより、2017年末までに量子優位性を実証する意向を発表した<ref name=":9">{{Cite news|url=https://spectrum.ieee.org/computing/hardware/google-plans-to-demonstrate-the-supremacy-of-quantum-computing|title=Google Plans to Demonstrate the Supremacy of Quantum Computing|newspaper=IEEE Spectrum: Technology, Engineering, and Science News|accessdate=2018-01-11}}</ref>。当時時の古典的なスーパーコンピュータで実行されている最大のユニバーサル量子回路シミュレータは、48量子ビットまでシミュレートすることが出来た<ref>{{Cite journal|last=Hans De Raedt|last2=Fengping Jin|last3=Dennis Willsch|last4=Madita Willsch|last5=Naoki Yoshioka|last6=Nobuyasu Ito|last7=Shengjun Yuan|last8=Kristel Michielsen|date=November 2018|title=Massively parallel quantum computer simulator, eleven years later|journal=Computer Physics Communications|volume=237|pages=47-61|DOI=10.1016/j.cpc.2018.11.005}}</ref>。しかしその後、特定の種類の回路においては、56量子ビットまでの量子回路がシミュレーション可能となった<ref>{{Cite arXiv|arxiv=1710.05867|class=quant-ph|last=Edwin Pednault|last2=John A. Gunnels|title=Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits|date=October 2017}}</ref>ため、量子優位性を実証するための[[量子ビット]]数を増やす必要が生じた<ref name=":8">{{Cite web|url=https://www.newscientist.com/article/2151032-googles-quantum-computing-plans-threatened-by-ibm-curveball/|title=Google's quantum computing plans threatened by IBM curveball|date=October 20, 2017|accessdate=October 22, 2017}}</ref>。2019年10月23日、Googleは、フィデリティの高い[[量子論理回路]]によって作られた「Sycamore」という新しい53量子ビットプロセッサを開発して行った量子優位性実験の結果を、ネイチャーの記事「プログラム可能な超伝導プロセッサを使用した量子優位性」で公開した 。 Googleは彼らのマシンが200秒で目的の計算を実行したと主張し、古典的なアルゴリズムは同じ問題を解決するために世界最速のスーパーコンピューターで10,000年かかると推定した<ref>{{Cite web|url=https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html|title=Quantum Supremacy Using a Programmable Superconducting Processor|website=Google AI Blog|accessdate=2019-11-02}}</ref>。IBMはこの主張に異議を唱え、従来のアルゴリズムを改良すれば、同じスーパーコンピューターで2日半でその問題を解決できるはずであると述べた<ref>{{Cite news|last=Metz|first=Cade|title=Google Claims a Quantum Breakthrough That Could Change Computing|url=https://www.nytimes.com/2019/10/23/technology/quantum-computing-google.html|accessdate=14 January 2020|newspaper=The New York Times|date=23 October 2019}}</ref>。 

== 懐疑論 ==
[[量子コンピュータ]]は、 [[量子デコヒーレンス|デコヒーレンス]]と[[ノイズ (電子工学)|ノイズ]]により、従来のコンピュータよりもはるかにエラーの影響を受けやすい<ref name="Kalai">{{Cite arXiv|arxiv=1106.0485|class=quant-ph|last=Kalai|first=Gil|title=How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation|date=2011-06-02}}</ref>。[[量子しきい値定理]]は、ノイズの多い量子コンピューターは[[量子エラー訂正|量子エラー修正]]コードを使用して<ref>{{Cite journal|last=Shor|first=Peter W.|date=1995-10-01|title=Scheme for reducing decoherence in quantum computer memory|journal=Physical Review A|volume=52|issue=4|pages=R2493–R2496|bibcode=1995PhRvA..52.2493S|DOI=10.1103/PhysRevA.52.R2493|PMID=9912632}}</ref><ref>{{Cite journal|last=Steane|first=A. M.|date=1996-07-29|title=Error Correcting Codes in Quantum Theory|journal=Physical Review Letters|volume=77|issue=5|pages=793–797|bibcode=1996PhRvL..77..793S|DOI=10.1103/PhysRevLett.77.793|PMID=10062908}}</ref>、各コンピューターサイクルで発生するエラーがある値よりも小さいことを前提にして、ノイズのない量子コンピューターをシミュレートできることを示している<ref>{{Cite arXiv|arxiv=quant-ph/9906129|last=Aharonov|first=Dorit|last2=Ben-Or|first2=Michael|title=Fault-Tolerant Quantum Computation With Constant Error Rate|date=1999-06-30}}</ref>。数値シミュレーションによると、許容されるエラー率は3％に達する<ref>{{Cite journal|last=Knill|first=E.|date=2005-03-03|title=Quantum computing with realistically noisy devices|journal=Nature|volume=434|issue=7029|pages=39–44|arxiv=quant-ph/0410199|bibcode=2005Natur.434...39K|DOI=10.1038/nature03350|ISSN=0028-0836|PMID=15744292}}</ref>。ただし、[[量子エラー訂正]]に必要なリソースが[[量子ビット]]の数に応じてどのように増えるのかはわかっていない<ref>{{Cite arXiv|arxiv=1605.00992|class=quant-ph|last=Kalai|first=Gil|title=The Quantum Computer Puzzle (Expanded Version)|date=2016-05-03}}</ref>。懐疑論者は、量子計算を成功させ量子優位性を実証するためには、大規模化した量子システムにおける未知のノイズの振る舞いが障害になると指摘している<ref>{{Cite book|last=Dyakonov|first=M. I.|chapter=Is Fault-Tolerant Quantum Computation Really Possible?|title=Future Trends in Microelectronics. Up the Nano Creek|editor=S. Luryi|publisher=Wiley|year=2007|pages=4–18|arxiv=quant-ph/0610117|bibcode=2006quant.ph.10117D}}</ref>。 

量子計算の研究の成果として、古典計算におけるアルゴリズムの進歩があり、その結果として古典コンピュータと性能が同等になると言う事も起きてきた。 これは、あるレベルでは、量子優位性は、量子計算と同等のパフォーマンスを持つ古典アルゴリズムが存在しないと言う、[[消極的事実の証明|否定の証明]]をしようとしていることになる<ref>{{Cite book|last=Tang|first=Ewin|date=2019-05-09|chapter=A quantum-inspired classical algorithm for recommendation systems|arxiv=1807.04271v3|doi=10.1145/3313276.3316310|title=Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019|pages=217–228|isbn=9781450367059}}</ref>。 

== 論争 ==

=== 名前の選択 ===
一部の研究者は、「超越性（supremacy）」という言葉が[[白人至上主義]]（White supremacy）の人種差別的な信念を想起させるため「量子超越性」と言う言葉を使用すべきではないと主張している。 [[ネイチャー]]に掲載された13人の研究者によって署名された解説は、代わりに「[[量子優位性]]（quantum advantage）」と言う言葉を使用すべきであると主張し<ref>{{Cite journal|last=Palacios-Berraquero|first=Carmen|last2=Mueck|first2=Leonie|last3=Persaud|first3=Divya M.|date=2019-12-10|title=Instead of 'supremacy' use 'quantum advantage'|journal=Nature|volume=576|issue=7786|pages=213|language=en|DOI=10.1038/d41586-019-03781-0|PMID=31822842}}</ref>、議論を呼んだ<ref>{{Cite web|url=https://www.wsj.com/articles/achieving-quantum-wokeness-11576540808|title=Opinion {{!}} Achieving Quantum Wokeness|author=Board|first=The Editorial|website=WSJ|language=en-US|accessdate=2019-12-21}}</ref><ref>{{Cite news|url=https://www.telegraph.co.uk/science/2019/12/17/academics-derided-claiming-quantum-supremacy-racist-colonialist/|title=Academics derided for claiming 'quantum supremacy' is a racist and colonialist term|last=Knapton|first=Sarah|date=2019-12-17|newspaper=The Telegraph|accessdate=2019-12-21|language=en-GB|issn=0307-1235}}</ref>。 [[カリフォルニア工科大学]]の理論物理学の教授でこの用語を作ったジョン・プレスキルは、「量子コンピューターが古典的なコンピューターではできないタスクを、それが役に立つか否かにかかわらず、できるようになる時点を表すために『量子超越性』と言う言葉を作った。 この新しい言葉で、我々が今、量子物理の原理に基づく情報技術が優位となる特別な時代にいることを強調したかった<ref>{{Cite web|url=https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/|title=John Preskill Explains ‘Quantum Supremacy’|website=Quanta Magazine|language=en|accessdate=2020-04-21}}</ref>」と述べた。彼はさらに「他のいくつかの可能性を考慮したが、採用しなかった。量子超越性が私が伝えたいポイントを最もよく捉えていたので決めた。 1つの選択肢は『量子優位性』で、これも現在広く使用されている。 しかし、私にとって、『優位性』には『超越性』ほどのパンチがない。 競馬では[[着差 (競馬)|ハナ差]]で勝っても優位だが、量子コンピュータの速度は、特定のタスクについて、古典的なコンピュータの速度を大幅に上回る<ref>{{Cite web|url=https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/|title=John Preskill Explains ‘Quantum Supremacy’|website=Quanta Magazine|language=en|accessdate=2020-04-21}}</ref>」と述べた。

== 関連項目 ==
* [[:en:List of quantum processors|量子プロセッサのリスト]] 
* [[:en:Sycamore processor|Sycamoreプロセッサ]]: 2019年にランダム数字分類タスクで50倍の量子超越性を達成したと主張されている 。 <ref name="NAT-20191023">{{Cite journal|last=Arute, Frank|date=23 October 2019|title=Quantum supremacy using a programmable superconducting processor|journal=[[Nature (journal)|Nature]]|volume=574|issue=7779|pages=505–510|bibcode=2019Natur.574..505A|DOI=10.1038/s41586-019-1666-5|PMID=31645734}}</ref><ref>{{Cite web|author=Martinis|first=John|title=Quantum Supremacy Using a Programmable Superconducting Processor|url=https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html|website=Google AI Blog|publisher=Alphabet|accessdate=5 December 2019|language=en}}</ref>

== 参考文献 ==
{{Reflist|15em}}

{{量子コンピュータ}}

{{DEFAULTSORT:りようしちようえつせい}}
[[Category:計算複雑性理論]]