量子優位性

量子コンピューティングにおいて、量子優位性または量子優位性は、問題の有用性に関係なく、従来のコンピュータでは実行可能な時間内に解決できない問題を、プログラム可能な量子コンピュータが解決できることを実証するという目標です。 ^{[1] [2] [3]}この用語は2012年にジョン・プレスキルによって造られましたが、^{[1] [4]}その概念は、ユーリ・マニンの1980年^[5]とリチャード・ファインマンの1981年^[6]の量子コンピューティングの提案にまで遡ります。

概念的には、量子超越性には、強力な量子コンピュータを構築するというエンジニアリングタスクと、その量子コンピュータで解決でき、そのタスクに対する最もよく知られている、または考えられる古典的なアルゴリズムよりも超多項式的に高速化できる問題を見つけるという計算複雑性理論のタスクの両方が含まれます。^{[7] [8]}

量子優位性を実証するための提案の例としては、アーロンソンとアルキポフによるボソンサンプリング提案^[9]や、ランダム量子回路の出力のサンプリングなどがある。^{[10] [11]ボソンサンプリングや}量子ランダム回路サンプリングで測定を行うことで得られる出力分布は平坦であるが、量子実験によって生成された分布に近い分布から古典的に効率的にサンプリングできないような構造になっている。この結論が有効であるためには、計算複雑性の理論における非常に緩やかな仮定のみを適用すればよい。この意味で、量子ランダムサンプリング方式は量子優位性を示す可能性を秘めている可能性がある。^[12]

量子超越性の注目すべき特性は、近い将来の量子コンピュータによって実現可能であることである。^[4]なぜなら、量子コンピュータは、有用なタスクを実行する必要がないため^[13]、または高品質の量子エラー訂正を使用する必要がないため^{[14] 、}どちらも長期的な目標である。^[2]そのため、研究者は量子超越性を主に科学的目標と見なし、量子コンピューティングの将来の商業的実現可能性に直接的な影響は比較的少ない。^[2]古典的なコンピュータとアルゴリズムの予測不可能な改善により、量子超越性は一時的または不安定である可能性があり、実現可能な成果は厳しい精査を受けることになる。^{[15] [16]}

1936年、アラン・チューリングは1900年のヒルベルト問題に応えて論文「計算可能数について」^[17]を発表しました。チューリングの論文では彼が「万能計算機」と呼んだものについて説明されており、これは後にチューリングマシンとして知られるようになりました。1980年、ポール・ベニオフはチューリングの論文を使用して量子コンピューティングの理論的実現可能性を提案しました。彼の論文「物理システムとしてのコンピュータ：チューリングマシンによって表現されるコンピュータの微視的量子力学的ハミルトンモデル」^[18]は、散逸するエネルギーが任意に小さい限り、量子コンピューティングの可逆的な性質を示すことが可能であることを初めて実証しました。1981年、リチャード・ファインマンは量子力学は古典的なデバイスでは効率的にシミュレートできないことを示しました。^[19]講義中に彼は有名な言葉を残した。「自然は古典的ではない。自然のシミュレーションを作りたいなら、量子力学的にした方がいい。そして、それは素晴らしい問題だ。それほど簡単には見えないからだ。」^[19]その後すぐに、デイヴィッド・ドイチュは量子チューリングマシンの説明を作成し、量子コンピュータで動作するように作成されたアルゴリズムを設計した。 ^[20]

1994年、ピーター・ショアがショアのアルゴリズムを定式化し、整数を多項式時間で因数分解する方法を合理化し、量子超越性に向けたさらなる進歩が遂げられました。 ^[21] 1995年、クリストファー・モンローとデビッド・ワインランドは「基本的な量子論理ゲートの実証」と題する論文を発表しました。^{[22]これは、}量子論理ゲート、具体的には2ビットの「制御NOT 」の最初の実証となりました。1996年、ロブ・グローバーは、論文「データベース検索のための高速量子力学アルゴリズム」の中で、グローバーのアルゴリズムというアルゴリズムを発表した後、量子コンピュータの製造への関心を高めました。^[23] 1998年、ジョナサン・A・ジョーンズとミシェル・モスカは「核磁気共鳴量子コンピュータ上でのドイチェ問題の解決のための量子アルゴリズムの実装」を発表し、^[24]量子アルゴリズムの最初の実証を行った。

2000年代には、初の5量子ビット核磁気共鳴コンピュータ（2000年）、ショアの定理の実証（2001年）、クラスター化量子コンピュータでのドイチェのアルゴリズムの実装（2007年）など、量子超越性に向けた大きな進歩がありました。 ^[25] 2011年、カナダのブリティッシュコロンビア州バーナビーのD-Wave Systemsは、量子コンピュータを商業的に販売した最初の企業となりました。^[26] 2012年、物理学者のNanyang Xuは、改良された断熱因数分解アルゴリズムを使用して143を因数分解するという画期的な成果を達成しました。しかし、Xuが使用した方法は反対に遭いました。^[27]この成果のすぐ後、Googleは最初の量子コンピュータを購入しました。^[28]

Googleは2017年末までに49個の超伝導量子ビットのアレイで量子超越性を実証する計画を発表していた。^[29] 2018年1月初旬、Intelは同様のハードウェアプログラムを発表した。^[30] 2017年10月、IBMは56個の量子ビットのシミュレーションを従来のスーパーコンピューターで実証し、量子超越性を確立するために必要な計算能力を高めた。^{[31] 2018年11月、Googleは}NASAとの提携を発表し、「Googleの量子プロセッサで実行される量子回路の結果を分析し、従来のシミュレーションとの比較を提供して、Googleのハードウェアの検証をサポートし、量子超越性のベースラインを確立する」ことを目指していた。^{[32] 2018年に発表された理論的研究によると、エラー率を十分に低く抑えることができれば、「7×7}量子ビットの2次元格子と約40クロックサイクル」で量子超越性が可能になるはずだと示唆されている。^[33]議論された方式は、量子ビットがユニバーサルゲートセットから抽出された量子ゲートを備えたランダム量子回路を通過し、その後計算基底で測定が行われる量子ランダムサンプリング方式の変形であった。

2019年6月18日、Quanta Magazineは、ネブンの法則によれば、量子超越性は2019年に実現する可能性があると示唆した。^[34] 2019年9月20日、Financial Timesは、「Googleは、53が機能する54個の量子ビットの配列で量子超越性を達成したと主張している。これらの量子ビットは、スーパーコンピューターでは約1万年かかる一連の操作を200秒で実行するために使用された」と報じた。^{[35] [36]} 10月23日、Googleは正式にその主張を認めた。^{[37] [38] [39]} IBMは、一部の主張は誇張であり、1万年ではなく2.5日で完了する可能性があると示唆し、古典的なスーパーコンピューターが計算速度を最大化するために使用する可能性のある手法を列挙して反論した。IBMの回答は、当時最も強力なスーパーコンピューターであるSummitがIBMによって製造されたため、関連性がある。^{[40] [15] [41]}研究者たちはその後、量子超越性を主張するために使用されたサンプリング問題に対するより優れたアルゴリズムを開発し、GoogleのSycamoreプロセッサと従来のスーパーコンピュータとの差を大幅に縮め^{[42] [43] [44]}、さらにはそれを上回った。^{[45] [46] [47]}

2020年12月、潘建偉氏が率いる中国科学技術大学（USTC）のグループは、光子量子コンピュータJiuzhangを使用して76個の光子にガウスボソンサンプリングを実装し、量子超越性を達成しました。^{[48] [49] [50]}論文によると、量子コンピュータが200秒間で生成するサンプル数を生成するには、従来のスーパーコンピュータでは25億年の計算時間が必要になります。^[3]

2021年10月、USTCのチームは、Jiuzhang 2.0とZuchongzhiと呼ばれる2つのスーパーコンピューターを構築し、再び量子優位性を報告しました。光ベースのJiuzhang 2.0は、ガウスボソンサンプリングを実装して144モードの光干渉計から113個の光子を検出し、サンプリングレートを10 ²⁴ – 37光子の差であり、以前のJiuzhangと比べて10桁大きい。^{[51] [52]} Zuchongzhiは、効率的に動作するために極低温に保つ必要があるプログラム可能な超伝導量子コンピュータであり、ランダム回路サンプリングを使用して、66個のトランスモンの調整可能な結合アーキテクチャから56量子ビットを取得します。これは、GoogleのSycamore 2019の成果よりも3量子ビット向上しており、古典的なシミュレーションの計算コストが2〜3桁大きいことを意味します。^{[53] [54] [55]} 3番目の研究では、Zuchongzhi 2.1が「古典的なシミュレーションで」「Sycamoreよりも約6桁難しい」サンプリングタスクを完了したと報告されています。^[56]

2022年6月、ザナドゥは、グーグルとUSTCの実験を足し合わせたボソンサンプリング実験を報告した。彼らのセットアップでは、光ファイバーのループと多重化を使用して、ビームスプリッターのネットワークを1つに置き換え、再構成もより簡単に行えるようにした。彼らは、216のスクイーズモード（スクイーズ光は光子数分布に従うため、モードごとに1つ以上の光子を含めることができる）から平均125〜219の光子を検出し、以前の実験よりも5000万倍の高速化を実現したと主張している。^{[57] [58]}

2024年3月、D-Wave Systemsは、量子アニーリングベースのプロセッサを使用した実験で、テンソルネットワークやニューラルネットワークなどの古典的な方法よりも優れた性能を示したと報告した。同社は、既知の古典的なアプローチでは、妥当な時間枠内で量子シミュレーションと同じ結果を得ることはできないと主張し、量子優位性を主張した。実行されたタスクは、量子相転移によってクエンチされた磁気スピンシステムの非平衡ダイナミクスのシミュレーションであった。^[59]

複雑性の議論は、問題を解決するために必要な何らかのリソース（通常は時間またはメモリ）の量が、入力のサイズに応じてどのように変化するかに関するものです。この設定では、問題は入力された問題インスタンス（バイナリ文字列）と返されたソリューション（対応する出力文字列）で構成され、リソースは指定された基本操作、メモリ使用量、または通信を指します。ローカル操作のコレクションにより、コンピューターは出力文字列を生成できます。回路モデルとそれに対応する操作は、古典的問題と量子的問題の両方を説明するのに役立ちます。古典的な回路モデルは、ANDゲート、ORゲート、NOTゲートなどの基本操作で構成され、量子モデルは古典的な回路とユニタリ操作の適用で構成されます。古典的なゲートの有限セットとは異なり、ユニタリ操作の連続的な性質により、量子ゲートの数は無限です。古典的および量子的な両方のケースで、問題のサイズが大きくなるにつれて複雑性が増大します。^{[60]古典的な}計算複雑性理論の拡張として、量子複雑性理論は、物理的な量子コンピューターの構築の難しさやデコヒーレンスとノイズへの対処を考慮せずに、理論上の汎用量子コンピューターが何を達成できるかを検討します。^[61]量子情報は古典情報の一般化であるため、量子コンピュータはあらゆる古典アルゴリズムをシミュレートすることができます。^[61]

量子複雑性クラスは、共通の量子計算モデルを共有する問題の集合であり、各モデルには指定されたリソース制約が含まれています。回路モデルは、量子複雑性クラスを説明するのに役立ちます。^[62]最も有用な量子複雑性クラスは、BQP（制限誤差量子多項式時間）であり、これは、汎用量子コンピュータによって多項式時間で解決できる決定問題のクラスです。 BQPと多項式時間階層の関係、BQPにNP完全問題が含まれているかどうか、BQPクラスの正確な下限と上限など、BQPに関する質問はまだ残っています。これらの質問への回答は、BQPの性質を明らかにするだけでなく、難しい古典的な複雑性理論の質問にも答えます。 BQPをよりよく理解するための1つの戦略は、関連するクラスを定義し、それらを従来のクラス階層に順序付けてから、BQPとの関係によって明らかになる特性を探すことです。^{[63]量子複雑性クラスには、} QMA（量子マーリンアーサー）やQIP（量子インタラクティブ多項式時間）など、他にもいくつかあります。 ^[62]

古典的なコンピューティングではできないことを証明することの難しさは、量子超越性を決定的に実証する上で共通の問題です。はいまたはいいえの回答を必要とする決定問題とは対照的に、サンプリング問題は確率分布からのサンプルを求めます。^{[64]任意の}量子回路の出力から効率的にサンプリングできる古典的なアルゴリズムがある場合、多項式階層は第3レベルに縮小しますが、これは一般的に非常にありそうにないと考えられています。^{[10] [11]}ボソンサンプリングはより具体的な提案であり、その古典的な困難さは、複素数エントリを持つ大きな行列のパーマネントを計算することの扱いにくさに依存しており、これは#P完全問題です。^[65]この結論に達するために使用された議論は、問題の平均および最悪のケースの複雑さが同じであるという推測のみが必要なIQPサンプリング^[66]や、 Google ^[38]とUSTCの研究グループによって再現されたタスクであるランダム回路サンプリング^[11]に拡張されています。^[48]

以下は、NISQデバイスと呼ばれる現在の技術を使用して量子計算の優位性を実証するための提案である。^[2]このような提案には、(1)明確に定義された計算問題、(2)この問題を解決するための量子アルゴリズム、(3)この問題を解決するための比較ベストケースの古典的アルゴリズム、(4)合理的な仮定の下では、古典的アルゴリズムは現在のアルゴリズムよりも大幅に優れたパフォーマンスを発揮できないという複雑性理論的議論（したがって、量子アルゴリズムは依然として超多項式速度向上を提供する）が含まれる。^{[7] [67]}

このアルゴリズムは、 nビット整数の素因数分解を1 時間で求めます^[68]。一方、最もよく知られている古典的なアルゴリズムは時間がかかり、この問題の複雑さの最良の上限は です。^{[69]また、奇数次の}体上の行列群のメンバーシップ問題など、整数因数分解に帰着するあらゆる問題を高速化できます。^[70]${\displaystyle {\tilde {O}}(n^{3})}$${\displaystyle 2^{O(n^{1/3})}}$${\displaystyle O(2^{n/3+o(1)})}$

このアルゴリズムは量子コンピューティングにとって実用的にも歴史的にも重要である。これは、古典的コンピュータでは困難であると考えられていた現実世界の問題に対して提案された最初の多項式時間量子アルゴリズムであった。 ^[68]すなわち、このアルゴリズムは、確立された暗号システムであるRSAが安全であるという合理的な仮定の下で、超多項式的な高速化をもたらす。^[71]

因数分解は、因数分解アルゴリズムが手に負えないほど遅い大きなインスタンスであっても、古典的なコンピュータで整数を掛け合わせるだけで素早く確認できるため、他の超越性提案に比べていくつかの利点があります。しかし、ショアのアルゴリズムを大きな数に実装することは現在の技術では実現不可能であるため、 ^{[72] [73]}超越性を証明するための戦略としては追求されていません。

線形光ネットワークを介して同一の光子を送信することに基づくこの計算パラダイムは、いくつかの複雑性理論的推測（ガウス行列のパーマネントを計算することは#P 困難であり、多項式階層は崩壊しない）を前提とすると、古典的なコンピュータでは処理不可能な特定のサンプリングおよび検索問題を解決することができます。^{[9]ただし、十分に大きな損失とノイズを持つシステムでの}ボソンサンプリングは効率的にシミュレートできることが示されています。 ^[74]

ボソンサンプリングのこれまでの最大の実験的実装は6つのモードを持っており、一度に最大6つの光子を処理できました。^[75]ボソンサンプリングをシミュレートするための最良の提案された古典的なアルゴリズムは、 n個の光子とm個の出力モードを持つシステムで時間内に実行されます。 ^{[76] [77] BosonSamplingは、} Rプログラミング言語のオープンソース実装です。このアルゴリズムは、ボソンサンプリングで量子優位性を証明するために必要な光子は50個であると推定します。 ^{[76] [77]}${\displaystyle O(n2^{n}+mn^{2})}$

任意のランダム量子回路をシミュレートする最もよく知られたアルゴリズムでは、量子ビットの数に比例して増加する時間が必要であるため、あるグループは約50量子ビットで量子超越性を実証するのに十分であると推定しています。^[33] Bouland、Fefferman、Nirkhe、Vazirani ^{[11]は2018年に、ランダム量子回路を効率的にシミュレートするには}計算多項式階層の崩壊が必要であるという理論的証拠を示しました。Googleは、現在のどの古典的コンピュータでも妥当な時間でアクセスできない分布をサンプリングできる49量子ビットのチップを構築して実行することにより、2017年末までに量子超越性を実証する意向を発表しました。^[29]当時古典的なスーパーコンピュータで実行されていた最大の汎用量子回路シミュレータは、48量子ビットをシミュレートできました。^[78]しかし、特定の種類の回路では、56量子ビットのより大きな量子回路シミュレーションが可能です。^[79]量子超越性を実証するには、量子ビットの数を増やす必要があるかもしれない。^[31] 2019年10月23日、GoogleはNatureの記事「プログラム可能な超伝導プロセッサを使用した量子超越性」でこの量子超越性実験の結果を発表し、ベンチマークテストを実行するために、高速で忠実度の高い量子論理ゲートが可能な「Sycamore」という新しい53量子ビットプロセッサを開発した。Googleは、自社のマシンが対象の計算を200秒で実行したと主張し、同社の古典的なアルゴリズムでは、世界最速のスーパーコンピューターで同じ問題を解くのに1万年かかると推定した。^[80] IBMはこの主張に異議を唱え、改良された古典的なアルゴリズムは同じスーパーコンピューターで2日半でその問題を解くことができるはずだと述べた。^{[81] [82] [83]}

量子コンピュータは、デコヒーレンスとノイズのために、古典的コンピュータよりもエラーの影響を受けやすい。^[84]閾値定理によれば、ノイズの多い量子コンピュータは、各コンピュータサイクルで導入されるエラーがある数値未満であると仮定すれば、量子エラー訂正コード^{[85] [86]}を使用してノイズのない量子コンピュータをシミュレートできる。^[87]数値シミュレーションでは、その数値は 3% にも達する可能性があることが示唆されている。^{[88]ただし、}エラー訂正に必要なリソースが量子ビットの数に応じてどのようにスケーリングされるかはまだ明確にわかっていない。 [89]懐疑論者は、スケールアップされた量子システムにおけるノイズの未知の動作が、量子コンピューティングの実装を成功させ、量子優位性を実証する上での潜在的な障害であると指摘している。^{[ 84] [90]}

一部の研究者は、「量子超越性」という用語は使用すべきではないと示唆し、「超越性」という言葉は白人至上主義という人種差別的信念との不快な比較を想起させると主張している。13人の研究者が署名した、ネイチャー誌の物議を醸した^{[91] [92]}論評記事は、代わりに「量子優位性」という代替語を使用するべきだと主張している。^{[93]この用語を作った}カリフォルニア工科大学の理論物理学教授ジョン・プレスキルは、その後、この用語は、量子コンピュータが古典的なコンピュータでは決して実行できなかったタスクを実行する能力を獲得した瞬間を明確に説明するために提案されたことを明らかにした。さらに彼は、「量子優位性」という用語が彼の新しい用語の意味を完全に包含していないため、特に拒否したと説明した。「優位性」という言葉は、量子超越性を備えたコンピューターが古典的なコンピューターよりもわずかに優れていることを意味しますが、「超越性」という言葉は、古典的なコンピューターに対する完全な優位性をよりよく伝えます。^[4]ネイチャーのフィリップ・ボールは2020年12月に、「量子優位性」という用語が「量子超越性」という用語に「ほぼ取って代わった」と書いています。^[94]

• ゴッテスマン・ニル定理
• 量子プロセッサのリスト
  • シカモアプロセッサー
  • 九章（量子コンピュータ）
• ノイズの多い中規模量子時代