Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling

全体像：「量子マジック」への挑戦

想像してみてください。それは「パターンの推測」という、非常に重要なゲームです。科学者たちは、量子コンピュータには、通常のコンピュータには不可能なことができると主張してきました。それは、特定の種類のランダムな文字列（デジタルなコイン投げのシーケンスのようなもの）を生成することです。このシーケンスは非常に複雑で、古典的なコンピュータでは決して予測もコピーもできないとされています。このタスクは**ランダム回路サンプリング（RCS）**と呼ばれ、量子コンピュータが古典的なコンピュータよりも優れていることを示す主要な証拠として使われてきました。

この論文の著者である Sangchul Oh 氏はこう言います。「ちょっと待ってください。これをするのに量子コンピュータは必要ありません。私は普通のノートパソコンで、しかももっと速く実行できます。」

核となるアイデア：「凍った木（Frozen Tree）」

著者がどのようにこれを行ったのかを理解するために、巨大で魔法のような木の比喩を使ってみましょう。

1. 量子の主張： 量子コンピュータがランダム回路を実行すると、「可能性の森」が作られます。コンピュータに答えを求めるたびに、その森の中のどこかの経路を選び出します。主張によれば、この森はあまりにも混沌としていて絡み合っているため、古典的なコンピュータ（あなたのノートパソコンのようなもの）には、その森のルールを解明して同じ経路を選ぶことはできないというのです。
2. 著者の発見： 著者は、この「混沌とした森」には、実は隠された完璧な構造があることを見つけました。それは二分木（バイナリツリー）（すべての枝が2つに分かれる木）の形をしています。
   • 頂上（ルート）で、木は分かれます。
   • 次のレベルで、それらの枝は再び分かれます。
   • これが繰り返され、最終的に底にある「葉」に到達します。これが最終的な0と1を表します。

秘密の鍵は、「条件付きスケール不変性（Conditional Scale Invariance）」と呼ばれるルールです。平たく言えば、これはこの木が**自己相似的（セルフ・シミラー）**であることを意味します。一番上の部分での枝分かれの様子は、中間地点での分かれ方や、葉の直前での分かれ方と、統計的に同一に見えます。これはフラクタルのようなものです。つまり、全体のパターンが、それぞれの小さな断片の中に繰り返されているのです。

「凍結（Frozen）」のトリック

ここからが巧妙な部分です。著者は、この量子的な木をシミュレートするために、一度にすべてを計算する必要はないことに気づきました。ただ、木の中を歩きながら構築していけばよいのです。

• 歩行： 木の頂上から葉に向かって歩いているところを想像してください。道の分岐点に到着するたびに、「左（0）に行くか、右（1）に行くか」を決めなければなりません。
• 「凍結」の瞬間： 本物の量子実験では、これらの決定は量子マシンによって行われます。著者の古典的な手法では、ある分岐点に初めて到着したとき、特別なコインを投げて、その分岐の比率（左に行く確率と右に行く確率の割合）を決定します。
  • 極めて重要な点： そのコインを投げて、その特定の分岐における比率を決めたら、それを**「凍結（フリーズ）」**させます。その値を書き留めておくのです。
  • もし、あなた（あるいは他の誰か）が再び同じ分岐点を訪れたとしても、その時も、最初に決めた全く同じ凍結された比率を使用します。二度とコインを投げ直したりはしません。

このように木が「凍結」されているため、著者はこれらのランダムな文字列を信じられないほど速く生成することができます。論文によれば、これには O(n) の時間しかかかりません。これは、ビット数が2倍になれば、作業量も2倍になるだけで、線形的かつ効率的であることを意味します。

「統計的な双子」の議論

この論文は、結果について非常に強力な主張を行っています。

• 量子の結果： 量子コンピュータは、特定のランダム回路に基づいた数値のリストを生成します。
• 古典的な結果： 「凍った木（Frozen-Tree）」アルゴリズムは、木の構造に基づいた数値のリストを生成します。

著者は数学的に、両方のリストが全く同じ統計的家族（ディリクレ分布と呼ばれます）から来ていることを証明しています。

これは、2人の異なるパン屋がチョコチップクッキーを作っているようなものです。

• パン屋A（量子）は、秘密の混沌としたオーブンを使っています。
• パン屋B（古典）は、精密に作られた凍結された型を使っています。

論文は、もし目隠しをした審査員に、パン屋Aのクッキーとパン屋Bのクッキーを渡したとしても、彼らはその違いを判別できないと主張しています。クッキー（データ）は統計的に同一なのです。

なぜこれが重要なのか（論文による説明）

現在、科学者たちはこう言っています。「見てください！量子コンピュータは、古典的なコンピュータには作れない、この奇妙で複雑なパターンを生み出しました。したがって、量子コンピュータが勝っています。」

著者はこう反論します。「それは間違いです。私たちは、古典的なコンピュータが『凍った木』の手法を用いることで、これと全く同じパターンを即座に生成できることを示しました。」

もし古典的なコンピュータが、その量子出力を完璧に模倣できるのであれば、この特定のテストにおける「量子優位性」（量子コンピュータが古典的なコンピュータにはできないことを行っているという考え）は消滅してしまうのです。

「ノイズ」の要因

本物の量子コンピュータは乱雑であり、ミス（ノイズ）を犯します。論文はまた、凍った木の手法がこれらのミスを簡単に模倣できることも示しています。量子コンピュータが「脱分極ノイズ（ランダムな静電気）」、「振幅減衰（エネルギー損失）」、あるいは「読み出しエラー（結果の誤読）」のいずれであっても、古典的な凍った木はそれらのエラーを完璧にシミュレートできます。

論文は次のように結論付けています。単に最終的な数値のリスト（サンプル）のみに基づいたテストでは、量子コンピュータが何か特別なことをしていることを証明することはできません。難しさはランダム性そのものにあるのではなく、「量子コンピュータがどの特定の木を構築したのか」を見極めることにあります。しかし、統計的な結果が同一である以上、このベンチマークは失敗していると言わざるを得ません。

一文での要約

この論文は、ランダムな量子回路の「魔法」とは、実は隠された自己相似的な木の構造に過ぎず、古典的なコンピュータが木を下る際に決定を「凍結」させることで、それを完璧かつ瞬時に複製できるものであるため、現在の量子優位性のテストには欠陥があると主張しています。