スタンフォード大学とバークレー大学の新たな研究により、Google の「量子超越性」が覆されました。理論的には美しいが、実際には役に立たない

量子超越性、この言葉が生まれてから4年近くになります。

2019 年、Google の物理学者は、53 量子ビット マシンによる量子覇権の達成に成功したと発表しました。これは重要な象徴的なマイルストーンでした。

Nature に掲載された論文によると、量子システムは計算を完了するのにわずか 200 秒しかかかりませんでしたが、同じ計算は当時最も強力なスーパーコンピューターである Summit によって実行されました。約1万年かかりました。

量子超越性とは何ですか?

いわゆる「量子ヘゲモニー」または「量子アドバンテージ」（以下、「量子超越性」と呼びます）とは、量子コンピューターが完了できるタスクの範囲を超えていることを意味します実行可能な古典的なアルゴリズムのいずれかです。

これらのタスクが最先端の従来型スーパーコンピューターに配置されたとしても、計算時間が長い (多くの場合、数千年) ため、アルゴリズムは実用的な重要性を失います。

興味深いことに、2019 年の Google の結果では、量子覇権が達成されたとだけ述べられており、量子コンピューターが古典コンピューターを超えた具体的な事例については説明されていませんでした。

これは答えるのが難しい質問です。現在、量子コンピューターはエラーに悩まされており、エラーが蓄積して量子コンピューティングのパフォーマンスと安定性を損なう可能性があります。

実のところ、量子覇権の実現の分野と比較すると、科学者がさらに知りたいのは、量子コンピューターがますます大きくなるにつれて、古典的なアルゴリズムが追いついていけるかどうかという別の疑問です。

最終的には量子側が完全に距離を置き、この問題を完全に終わらせることを望んでいる、とテキサス大学のコンピューター科学者スコット・アーロンソン氏は述べた。オースティン。競争。」

ほとんどの研究者は、答えはノーであると推測しています。

つまり、古典的なアルゴリズムはいつか量子コンピューティングのペースにまったく追いつけなくなるのですが、これを正確かつ包括的に証明することはできていません。この推論を決定的に証明する 1 つの方法は、量子コンピューティングが従来のコンピューティングに対して「永続的な利点」を得ることができる条件を見つけることです。

さて、この質問には暫定的な答えがあるようです:

お金を節約: 量子コンピューティングではエラーが発生します。追いつけない場合、この種のエラーは理想的な状態の「量子覇権」を破壊し、古典的なアルゴリズムが量子アルゴリズムに追いつくことを可能にします。

##最近、Arxiv で公開されたプレプリント論文で、ハーバード大学、カリフォルニア大学バークレー校、イスラエルの共同チームの研究者が発表しました。武礼大学の博士は、この結論を確認するために大きな一歩を踏み出しました。

彼らは、ターゲットを絞った誤り訂正がランダム回路サンプリングにおける永続的な量子超越性の必要条件であることを実証し、数年前の Google の研究の結論を裏付けました。現在の量子誤り訂正レベルでは、量子覇権は実際には存在しません。

量子超越性の「ゴールデン ゾーン」はもう存在しない

研究者らは、この結論を証明するために、エラーが存在する場合にランダムな回路サンプリング実験をシミュレートできる古典的なアルゴリズムを開発しました。

量子ビットの配列から開始し、「量子ゲート」と呼ばれる操作を使用して量子ビットをランダムに操作します。一部の量子ゲートは量子ビットのペアをもつれさせます。これは、量子ビットが個別に記述できない量子状態を共有することを意味します。

多層回路でこれらの量子ゲートを繰り返し設定すると、量子ビットがより複雑なもつれ状態に入ることが可能になります。

#左の図は理想的な条件下でのランダム回路サンプリングを示し、右の図は干渉を含むランダム回路サンプリングを示します

順番にこの量子状態を理解するために、研究者らはアレイ内のすべての量子ビットを測定しました。この動作により、すべての量子ビットの集合的な量子状態が通常のビット、つまり 0 と 1 のランダムな文字列に崩壊します。

配列内の量子ビットの数に応じて、考えられる結果の数は急速に増加します。 Google の 2019 年の実験では、53 量子ビットに 10 兆近くの結果が含まれていました。

さらに、この方法では、結果の確率分布マップを構築するために、ランダム回路からの測定を何度も繰り返す必要があります。

量子超越性に関する疑問は、もつれをまったく使用しない古典的なアルゴリズムでこの確率分布を模倣するのは難しい、あるいは不可能であるということです。

2019 年、Google の研究者は、エラーを発生させないエラーフリーの量子回路ではこの目標が困難であることを実証しました。確かに、古典的なアルゴリズムを使用してランダム回路サンプリング実験をエラーなくシミュレートすることは困難です。

計算の複雑さの観点から見ると、量子ビットの数が増加すると、従来の分類アルゴリズムの計算の複雑さは指数関数的に増加しますが、量子アルゴリズムの計算の複雑さは多項式に増加します。

n が十分に大きくなると、n が指数関数的なアルゴリズムは、n が多項式のアルゴリズムよりもはるかに遅れます。

これは、古典的なコンピューターにとっては難しいが、量子コンピューターにとっては簡単な問題について話すときに言及している違いです。最良の古典的アルゴリズムは指数関数的な時間を要しますが、量子コンピューターは多項式時間で問題を解決できます。

しかし、2019 年の論文では不完全な量子ゲートによって引き起こされるエラーの影響が考慮されておらず、研究の結論には実際には穴が残されています。回路サンプリングによって実現できますか?

実際、量子もつれで発生し、蓄積される可能性がある誤差を考慮すると、古典的なアルゴリズムを使用してランダム回路サンプリング実験をシミュレートする難易度は大幅に軽減されます。そして、古典的アルゴリズムのシミュレーションの計算量が量子アルゴリズムと同じ多項式レベルまで低減されれば、量子覇権はもはや存在しなくなるでしょう。

この新しい論文は、回路の深さが一定に保たれていると仮定すると、たとえば非常に浅い 3 層であれば、量子ビットの数が増加しても、量子もつれはそれほど多くならないことを示しています。は引き続きクラシック シミュレーションで使用できます。

一方、量子ビット数の増加に対応するために回路の深さが増加すると、量子ゲートエラーの累積効果により、シミュレーションでエンタングルメントによって引き起こされる複雑さが薄れます。従来のアルゴリズムを使用すると、エクスポートはさらに簡単になります。

両者の間には「ゴールデン ゾーン」があります。つまり、量子覇権が存続し続けることができる範囲、つまり、従来のアルゴリズム シミュレーションでは追いつけない範囲です。量子のもつれ。

この論文が発表される前は、量子ビットの数が増加しても、量子ビットの数が特定の中間範囲に達すると量子超越性がまだ存在していました。

この回路の深さでは、たとえ量子アルゴリズムのエラーにより出力が着実に低下するとしても、古典的なアルゴリズムをすべてのステップでシミュレートすることは困難です。

この新しい論文では、この「ゴールデン ゾーン」がほぼ排除されています。

この論文は、ランダム回路サンプリングをシミュレートするための古典的なアルゴリズムを導き出し、その実行時間が、対応する量子実験の実行に必要な時間の 多項式関数であることを証明しています。指数関数ではなく、。

この結果は、ランダム回路サンプリングの古典的な方法の速度と量子方法との間に理論上の密接な関係を確立します。つまり、量子覇権が理論的に達成されたことを宣言します。実際には、それはほとんど存在しません。

私が「ほぼ」と言ったのは、新しいアルゴリズムの基本的な仮定が一部の浅い回路では無効であり、未知の「小さなギャップ」が残るためです。

しかし、このギャップにおいて量子超越性を達成する希望を抱いている研究者はまだほとんどいません。シカゴ大学のコンピューター科学者であり、2019年のGoogle論文の著者の一人であるビル・フェファーマンでさえ、「その可能性は非常に小さいと思う」と述べた。

計算複雑性理論の厳格な基準によれば、ランダム回路サンプリングでは量子超越性はもはや生み出されないと言えます。

また、この結論に直面して、すべての研究者は、量子コンピューティングの長期的な成功にとって量子誤り訂正がいかに重要であるかについて同意しています。フェファーマン氏は、「研究の結果、量子誤り訂正が解決策であることがわかりました。」と述べました。

以上がスタンフォード大学とバークレー大学の新たな研究により、Google の「量子超越性」が覆されました。理論的には美しいが、実際には役に立たないの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。