Approximating fixed size quantum correlations in polynomial time

アリスとボブという二人の友人が、広大な距離によって隔てられ、互いに会話することもできない世界を想像してみてください。しかし、彼らは賞品を獲得するために、ある見知らぬ人物の質問に対する答えを一致させなければなりません。古典的な世界では、彼らは事前に計画（例えば秘密のコードなど）を合意しておくのが最善の戦略です。しかし、量子的な世界では、彼らは「もつれ」と呼ばれる特別な「不気味な」つながりを共有することができます。これにより、彼らは通常の物体では不可能と思われるような方法で、答えを調整することができるのです。この設定は「非局所ゲーム」として知られており、現実の限界をテストするための遊び場となっています。科学者が問い続けてきた大きな疑問は、「アリスとボブがこれらの量子的トリックを用いた場合、彼らはどれほど上手く立ち回れるのか？」ということです。いくつかのゲームについては答えが出ていますが、多くのゲームにおいて、絶対的な最高勝率を計算することは非常に困難であり、コンピュータが合理的な時間内に解くことは不可能である可能性さえあります。それは、宇宙にある原子の数よりも多くの曲がり角がある迷路の中で、たった一つの最適な経路を見つけようとするようなものです。

ここで、研究チームが新しい巧妙なアプローチを提示します。彼らは、不可能な迷路を一度に解決しようとしているのではありません。代わりに、頂上にどんどん近づいていく一連の「近似の梯子（はしご）」を築いています。彼らの主な発見は、プレイヤーが固定された限られた量の量子的な力（特定のサイズの量子もつれ）を持っているゲームの場合、その精度を高めたい場合に、その精度に応じて合理的に増大する時間内で、非常に優れた勝率の推定値を計算できるということです。彼らは、プレイヤーが共有する量子状態を「同一の音符による交響曲」のように扱う新しい数学的ツールを発明することで、これを達成しました。これにより、計算における乱雑で反復的な部分を無視することができるようになったのです。これにより、かつては指数関数的な時間（宇宙の終焉を待つような時間）を要していた問題が、多項式的な時間（大きな数字まで数えるような時間）へと変わりました。彼らは単に答えを見つけただけでなく、彼らの数学的な推定値を、アリスとボブが実際に使用できる本物の、機能的な戦略へと変換する方法も構築し、彼らのショートカットが真の解決策につながることを証明しました。

量子ゲームショー

ゲームショーの司会者が、二人のプレイヤー、アリスとボブを別々の部屋に送り込む場面を想像してください。司会者はアリスに一つの質問を、ボブには別の質問をランダムに選びます。質問が出された後は、彼らは互いに話すことができません。しかし、ドアが閉まる前に、彼らは計画をささやくことができます。彼らの目標は何でしょうか？ それは、答えを秘密のルールに一致させることです。もし一致すれば、彼らは1ポイント獲得できます。

この「古典的」なバージョンのゲームでは、アリスとボブはコイン投げや事前に書かれた台本に従うといった標準的な戦略に制限されます。しかし、「量子」バージョンのゲームでは、彼らは「もつれ」と呼ばれる、不思議に結びついたリソースを共有することが許されています。もつれを、魔法のサイコロのペアだと考えてみてください。どれほど離れていても、もしアリスが「6」を出せば、ボブのダイスも即座に「6」を示します。たとえ、どちらも結果を見るまで何を出すか決めていなかったとしてもです。この「不気味な」つながりにより、彼らは古典物理学では不可能とされる方法で答えを調整でき、単なる台本に従うよりも高い確率でゲームに勝つことができる場合が多いのです。

科学者にとっての大きなパズルは、「彼らが勝ち得る絶対的な最大確率はいくらか？」ということです。単純なゲームであれば、答えは分かっています。しかし、より複雑なゲームの場合、その完璧な数値を求めることは悪夢です。問題は、可能な戦略の数が非常に速いスピードで増加するため、最速のスーパーコンピュータであっても、宇宙の年齢よりも長い時間をかけてチェックしなければならないということです。それは、一歩動くたびに盤面が倍々に大きくなっていくチェスの最善の一手を探すようなものです。

新しいショートカット：対称性と「ボース」の魔法

Julius Zeiss氏率いる研究チームは、力技（ブルートフォース）でこの問題に挑んだわけではありません。代わりに、プレイヤーが固定されたサイズの量子的な助け（つまり、「魔法のサイコロ」の面の数が決まっている）を持つゲームにおいては、そこには利用できる隠れたパターンが存在することに気づきました。

彼らはこの問題を、巨大で乱雑な図書館のように扱いました。通常、数十億冊の整理されていない本がある図書館の中から特定の１冊を探すには、膨大な時間がかかります。しかし、もしその本の99%が、表紙こそ違えど、実質的には同じ数種類のタイトルのコピーであると気づいたらどうでしょうか？ すべてのコピーを読む必要はなく、各タイプの代表的な一冊だけを読めばよいのです。

チームは「ボース対称性（Bose-symmetry）」と呼ばれる数学的概念を用いました。量子の世界では、粒子は「区別不可能」であり、二つの粒子を入れ替えても系の状態は変わりません。研究者たちは、これらのゲームにおける最適な戦略もしばしば、この「区別不可能」という特性を持っていることに気づきました。これらの対称的な戦略だけに焦点を当てることで、彼らは問題を、数十億冊の本がある図書館から、管理可能な小さな棚へと縮小することができました。

彼らは、**ボース対称階層（Bose-symmetric hierarchy）**と呼ぶ新しい手法を開発しました。これは、次のように段階的に精度を高めていく推測のプロセスです。

1. 最初の推測： 計算は容易ですが、少し高めの値になる可能性がある粗い近似（アウターバウンド）から始めます。
2. 洗練： より多くの対称性の制約を加えることで、推測をより厳密にし、真の答えに近づけます。
3. 結果： 彼らは、誤差をわずかな量（$\epsilon$と呼びましょう）に抑えるために、この梯子を一定の数だけ登る必要があることを証明しました。決定的なのは、この梯子を登るのにかかる時間は、$1/\epsilon$に対して多項式的に増大するという点です。

ここでの「多項式的」とはどういう意味でしょうか？ それは、もし精度を2倍にしたければ、コンピュータは単に作業量を2倍にするのではなく、4倍、あるいは8倍の努力が必要になるかもしれないという意味です。しかし、作業量が「無限」になることはありません。これは、以前の手法が「指数関数的」であったこと（精度の向上に伴い、時間が倍々ゲームで増えていき、最終的に無限に達してしまうこと）と比較して、劇的な改善です。

数学から現実へ：丸め（Rounding）のトリック

数値を求めることと、実際にゲームに勝つための戦略を見つけることは別物です。研究者たちは、単に勝率を計算するだけでは終わりませんでした。彼らはまた、「丸めスキーム（rounding scheme）」を考案しました。

ある計算の結果、最高のスコアが99.9%であると判明したとしましょう。しかし、そのスコアを得るために、具体的にどのようにプレイすればよいのでしょうか？ 彼らの手法は、簡略化された対称的な世界からの数学的な解を、現実のプレイ可能な戦略へと「丸める」ものです。彼らは測定プロセスをシミュレートすることでこれを行います。つまり、抽象的で完璧な解を取り出し、そこからアリスとボブが実際に実行できる具体的な指示（測定）を抽出するのです。

これは、まるで「夢の言語」で描かれた宝島の完璧な地図を持っているようなものです。研究者たちは、宝がどこにあるか（勝利確率）を突き止めただけでなく、その地図を、実際の探検家が従うことができる明確でステップ・バイ・ステップの指示へと翻訳する方法も見出したのです。彼らは、この翻訳された戦略が、最適解に極めて近いものであることが保証されていることを示し、ゲームに勝つための「実現可能な」方法を提供しました。

なぜこれが重要なのか

この研究は、量子情報理論における長年の課題を解決したため、非常に重要な意味を持ちます。長い間、科学者たちは、固定されたサイズの量子リソースを持つゲームについては、答えは計算可能であるはずだと分かっていましたが、それを効率的に行う方法を見つけられずにいました。従来の手法は「指数関数的な時間」に阻まれており、ごく小さなゲーム以外には役に立ちませんでした。

これらの問題が多項式時間で解けることを証明したことで、著者たちは、幅広い種類の量子ゲームを効率的に分析するための扉を開きました。これは単にゲームショーに勝つための技術ではありません。古典的世界と量子的世界の間の根本的な境界線を理解することに役立ちます。これにより、特定のシナリオにおいてどれほどの「量子的優位性」が可能であるかを正確に把握でき、それを達成するための戦略を見つけ出すための道具を手に入れることができるのです。

また、この論文は、これらの技術が量子コンピュータが正しく動作しているかを確認する（エラー訂正）ことや、二つの量子状態が本当に異なっているかどうかを判断することなど、他の困難な量子物理学の問題にも有用であることを示唆しています。しかし、現時点での主要な勝利は明白です。彼らは、対称性の力を利用してノイズを切り抜けることで、複雑で混乱した量子世界の中に潜む秩序を利用し、不可能な計算を管理可能なものへと変えたのです。

要するに、チームは、量子世界は複雑で混乱しているものの、そこには隠れた秩序が存在することを示しました。その秩序に耳を傾けることで、私たちは驚くべき速さと正確さで、量子ゲームの未来を予測できるのです。