Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling

コンピュータが単に数字を計算するだけでなく、光と踊る世界を想像してみてください。これは量子コンピューティングの領域であり、今日のスーパーコンピュータが挫折して諦めてしまうような問題を解決するために、量子世界の奇妙でゆらゆらとした規則を利用する機械の世界です。この世界における最も有名な「ダンスフロア」の一つが、**ボソン・サンプリング（Boson Sampling）**と呼ばれるものです。鏡とガラスのプリズムで作られた巨大で複雑な迷路（線形光学ネットワーク）を思い浮かべてください。あなたは、フォトンのと呼ばれる一連の同一の粒子（光の小さな塊）を片方の端から射出します。それらは跳ね返り、分裂し、そして混沌としていながらも完全に予測可能な量子的な方法で再結合します。それらが反対側に到達するとき、彼らは特定の場所に降り立ちます。課題は？彼らが正確にどこに降り立つかを予測することです。

通常のコンピュータにとって、これは、すべての投げられたコインが互いに影響を与え合いながら、同時に百万回のコイン投げが行われている結果を予想しようとするようなものです。それは非常に困難であり、古典的なコンピュータがそれを素早く行うことは不可能であると私たちは信じています。しかし、量子機械にとっては、それは単に光を遊ばせるだけの問題なのです。しかし、量子機械が単に運良く当たっているのではなく、実際に勝っていることを証明するために、科学者たちは光が退屈で予測可能な振る舞いをしていないことを確信する必要があります。彼らは、その「ダンス」が本当に荒々しく広がっており、隅の方に固まっていないことを証明しなければなりません。この概念は**反集中（anti-concentration）**と呼ばれます。もし光が固まりすぎれば、通常のコンピュータがその結果を偽造できてしまうかもしれません。もし光がちょうどよく広がっていれば、量子の優位性は本物となります。

ここで物語は数学的になります。フォトンの「ダンス」は、**パーマネント（permanent）**と呼ばれるトリッキーな数学的公式によって支配されています。これは、あなたが高校数学で見かけたかもしれない行列式（determinant）の従兄弟のようなものですが、数字を引く代わりに、加算のみを行います。このことが計算を極めて困難にしています。量子の優位性が成立するためには、ランダムな一組の数字（鏡やプリズムを表す）のパーマネントが、ほとんどの場合において「十分に大きく」ある必要があります。もし小さすぎると、数学が崩壊してしまいます。長年、科学者たちはこれが単純な離散的な数字（0や1のような）に対しては機能することを知っていましたが、光を記述する実際の複雑で波のような数字については行き詰まっていました。

これが、フェイ・メン、ビン・チェン、ジアナン・リ、そしてマン・ホン・ユングが新しい論文で取り組んだパズルです。彼らは謎のすべてを解いたわけではありませんが、大きな一歩を踏み出しました。彼らは、これらの複雑な、光のような数字のパーマネントが、通常は量子の優位性を維持できるほど十分に大きいというルールの**「弱い」バージョン**を証明しました。これは、嵐が確実に起きていることを、たとえ正確な風速を測定してハリケーンであることを証明していなくても、証明しているようなものです。彼らは、数学が使い物にならないほど小さな数に崩壊する確率が、信じられないほど低いこと、実質的にゼロであることを示しました。

彼らがどのように行ったかというと、「行露出（row-exposure）」戦略と呼ばれる巧妙なトリックを用いました。ブロックを使って塔を建てているところを想像してください。ただし、一度に一つの層しか見ることができません。過去には、ブロックが単純な立方体（離散的な数字）であれば、この塔が真っ直ぐ立つことを数学者は証明できました。しかし、これらの新しいブロックは、滑りやすい、回転する液体（複雑なガウス数）でできています。著者たちは、これらの滑りやすいブロックであっても、層ごとに積み上げていけば、塔が成長し続ける可能性が高いことに気づきました。彼らは、各ステップにおいて、塔の「高さ」（パーマネント）が、縮小して消えてしまうのではなく、大きくなる確かなチャンスがあることを示しました。

彼らは、これらの滑りやすいブロックを扱うために、いくつかの新しいツールを発明しなければなりませんでした。境界が定められた予測可能なものを扱う標準的な数学ツールは、ここでは機能しませんでした。なぜなら、これらの数字は無限に大きくなり得るからです。そこで、彼らは古い安全網を、より強力なもの（マクディアミドの不等式）へと入れ替えました。これは、制御不能で無制限な変動を扱うことができるものです。また、これらの数字が完璧な円を描いて回転している（回転対称性）という事実を利用して、塔が崩壊する可能性が低いことを論じました。

結果はどうだったでしょうか？彼らは、ランダムな一組のこれらの光の数字に対して、パーマネントがほぼ常に特定の大きなサイズ（およそ $n^{(1/2+o(1))n}$）であることを証明しました。これは、フォトンの「ダンス」が、固まってしまうことなく、確かに荒々しく広がっていることを裏付けています。しかし、彼らは自分たちが「何を行わなかったか」についても正直です。彼らは「弱い」バージョンを証明しました。つまり、数学が失敗する確率は非常に小さいものの、科学者が望む究極の「強い」バージョン（多項式分数のレベル）ほどではありません。彼らの証明は、失敗率が超指数関数的に小さい（$1/n^{\alpha n}$ のように）ことを示しており、これは依然として極めて小さいものですが、古典的なあらゆる「ズル」の道を完全に閉ざすための「完璧な」保証にはまだ達していません。

では、これは将来にとって何を意味するのでしょうか？それは、量子コンピュータが真に特別なことを行っているという確信に、私たちが一歩近づいたことを意味します。彼らの結果を既存の他の理論と組み合わせれば、もし古典的なコンピュータがこの光のダンスを完璧に模倣できるとしたら、それは計算機科学の論理体系全体（多項式階層の崩壊）を破壊してしまうことを示唆しています。これは極めて起こりにくいことです。彼らは問題の最も難しい部分に終止符を打ったわけではありませんが、「はい、量子のダンスは実在し、それは通常のコンピュータがコピーするには不可能なほど混沌としている」という非常に説得力のある章を書き上げました。それは、たとえ最終的な完璧なビートをまだ待っている状態であっても、光が踊っていることを示す堅実な証明なのです。