量子コンピューティングにおいて量子超越性（りょうしちょうえつせい、英: 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]。重要な古典的複雑性クラスの階層に関連付けらる${\displaystyle P\subseteq BPP\subseteq BQP\subseteq PSPACE}$^[30]。これらの包含関係が厳密かどうか（等号が成立しないかどうか）はどれも未解決の問題である。

古典的なコンピューティングでは計算できないことを証明する難しさは、量子優越性を示す上での一般的な課題である。 白黒をはっきりつける決定問題とは異なり、サンプリング問題は、ある確率分布からのサンプルを求める。^[31] 任意の量子回路の出力から効率的にサンプリングできる古典的なアルゴリズムがある場合、 多項式階層は第3レベルに折りたたまれるが、これはほとんどあり得ないと考えられてる。^[9] ボソンサンプリングは、より具体的な提案であり、その古典的な難しさは、複雑なエントリを持つ大きな行列のパーマネントを計算する難しさに依存する。これは、#P完全な問題である^[32]。この結論に到達するために使用された議論は、IQPサンプリング^[33]にも拡張され、そこでは問題の平均と最悪のケースの複雑さは同じであるという推測のみが必要となる。

以下は、現在NISQデバイスと呼ばれることが多い現在の技術を使用して、量子計算の優位性を実証するための提案である^[2]。そのような提案には、（1）明確に定義された計算上の問題、（2）その問題を解決するための量子アルゴリズム 、（3）最善の古典アルゴリズムとの比較、および（4）合理的な仮定の下では、現在存在する古典アルゴリズムが大幅に改善する見込みがないと言う計算複雑性理論上の議論、が含まれる（そのため、量子アルゴリズムはあらゆる古典アルゴリズムに対して超多項式の高速化を提供する）^[3][34]。

ショアのアルゴリズムは、 nビット整数の素因数分解を${\displaystyle {\tilde {O}}(n^{3})}$時間で行う^[35]。これに対して、知られている最善の古典アルゴリズムは${\displaystyle 2^{O(n^{1/3})}}$時間必要である。また、この問題の複雑さの最良の上界は${\displaystyle O(2^{n/3+o(1)})}$ である^[36]。このアルゴリズムは整数因数分解に帰着される全ての問題を高速化する。その中には奇数オーダーの可換体上の行列群のメンバーシップ問題が含まれる^[37]。

このアルゴリズムは、 量子コンピューティングにとって実用的にも歴史的にも重要である。古典コンピュータでは解くことの出来ないと信じられている現実の問題に対して提案された、最初の多項式時間量子アルゴリズムである^[35]。つまり、今日合理的に信じられている暗号化プロトコルであるRSAが安全であるという仮定の下で、このアルゴリズムは超多項式の高速化を実現する^[38]。

例え非常に大きな数の場合でも、因数分解は乗算するだけで従来のコンピューターですばやくチェックできるため、因数分解は他の量子優位性の提案よりも利点がある。ただし、Shorのアルゴリズムを大きな数に対して実装することは、現在の技術では不可能なため^[39][40]、優位性を実証するための戦略として追求されていない。

線形光学ネットワークを介して送信された同一の光子に基づくこの計算パラダイムは、古典アルゴリズムが(ガウス行列のパーマネントの計算が#P-Hardであり、 多項式階層が潰れないと言う、計算複雑性理論上の予想の下で）解くことが出来ない、特定のサンプリング及び検索問題を解くことができる^[7]。ただし、十分に大きな損失とノイズがあるシステムでのボソンサンプリングは、効率的にシミュレーションできることが示されている^[41]。

これまでのボソンサンプリングの最大の実験では、6つのモードがあり、一度に最大6つの光子を処理できた^[42]。時間内にボソンサンプリングの実行をシミュレートするための最善の古典アルゴリズムは、n個の 光子とm個の出力モードを持つシステムの場合、 ${\displaystyle O(n2^{n}+mn^{2})}$ 時間で動作する^[43][44]。BosonSamplingはRでのオープンソース実装である。このアルゴリズムによると、ボソンサンプリングで量子優位性を実証するためには、50個の光子が必要であると推定される。

任意のランダム量子回路をシミュレートするための最善のアルゴリズムの実行時間は、 量子ビット数に応じて指数関数的に増加する。あるグループは、およそ50量子ビットがあれば量子超越性を実証するのに十分であると推定した^[14]。Googleは、49 量子ビットチップを構築して、現在の古典的なコンピューターが妥当な時間内にアクセスできない確率分布を作ることにより、2017年末までに量子優位性を実証する意向を発表した^[10]。当時時の古典的なスーパーコンピュータで実行されている最大のユニバーサル量子回路シミュレータは、48量子ビットまでシミュレートすることが出来た^[45]。しかしその後、特定の種類の回路においては、56量子ビットまでの量子回路がシミュレーション可能となった^[46]ため、量子優位性を実証するための量子ビット数を増やす必要が生じた^[12]。2019年10月23日、Googleは、フィデリティの高い量子論理回路によって作られた「Sycamore」という新しい53量子ビットプロセッサを開発して行った量子優位性実験の結果を、ネイチャーの記事「プログラム可能な超伝導プロセッサを使用した量子優位性」で公開した 。 Googleは彼らのマシンが200秒で目的の計算を実行したと主張し、古典的なアルゴリズムは同じ問題を解決するために世界最速のスーパーコンピューターで10,000年かかると推定した^[47]。IBMはこの主張に異議を唱え、従来のアルゴリズムを改良すれば、同じスーパーコンピューターで2日半でその問題を解決できるはずであると述べた^[48]。

量子コンピュータは、 デコヒーレンスとノイズにより、従来のコンピュータよりもはるかにエラーの影響を受けやすい^[49]。量子しきい値定理は、ノイズの多い量子コンピューターは量子エラー修正コードを使用して^[50][51]、各コンピューターサイクルで発生するエラーがある値よりも小さいことを前提にして、ノイズのない量子コンピューターをシミュレートできることを示している^[52]。数値シミュレーションによると、許容されるエラー率は3％に達する^[53]。ただし、量子エラー訂正に必要なリソースが量子ビットの数に応じてどのように増えるのかはわかっていない^[54]。懐疑論者は、量子計算を成功させ量子優位性を実証するためには、大規模化した量子システムにおける未知のノイズの振る舞いが障害になると指摘している^[55]。

量子計算の研究の成果として、古典計算におけるアルゴリズムの進歩があり、その結果として古典コンピュータと性能が同等になると言う事も起きてきた。 これは、あるレベルでは、量子優位性は、量子計算と同等のパフォーマンスを持つ古典アルゴリズムが存在しないと言う、否定の証明をしようとしていることになる^[56]。

一部の研究者は、「超越性（supremacy）」という言葉が白人至上主義（White supremacy）の人種差別的な信念を想起させるため「量子超越性」と言う言葉を使用すべきではないと主張している。 ネイチャーに掲載された13人の研究者によって署名された解説は、代わりに「量子優位性（quantum advantage）」と言う言葉を使用すべきであると主張し^[57]、議論を呼んだ^[58][59]。 カリフォルニア工科大学の理論物理学の教授でこの用語を作ったジョン・プレスキルは、「量子コンピューターが古典的なコンピューターではできないタスクを、それが役に立つか否かにかかわらず、できるようになる時点を表すために『量子超越性』と言う言葉を作った。 この新しい言葉で、我々が今、量子物理の原理に基づく情報技術が優位となる特別な時代にいることを強調したかった^[60]」と述べた。彼はさらに「他のいくつかの可能性を考慮したが、採用しなかった。量子超越性が私が伝えたいポイントを最もよく捉えていたので決めた。 1つの選択肢は『量子優位性』で、これも現在広く使用されている。 しかし、私にとって、『優位性』には『超越性』ほどのパンチがない。 競馬ではハナ差で勝っても優位だが、量子コンピュータの速度は、特定のタスクについて、古典的なコンピュータの速度を大幅に上回る^[61]」と述べた。

• 量子プロセッサのリスト
• Sycamoreプロセッサ: 2019年にランダム数字分類タスクで50倍の量子超越性を達成したと主張されている 。 ^[20][62]

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