コンピュータサイエンスの証明が数学と物理学の答えを握る

2020年3月8日午前8時

量子コンピューティングに関する理解の進歩により、数学者や物理学者を長らく悩ませてきた問題に驚くべき解決策がもたらされています。

コンピュータサイエンスにおける新たな証明は、量子力学や純粋数学の研究者にも影響を与える。イラスト：DVDP/Quanta Magazine

1935 年、アルバートアインシュタインは、ボリスポドルスキーとネイサンローゼンと共同で、量子物理学の新しい法則によって明らかにされた可能性、つまり 2 つの粒子が遠く離れていても絡み合う、つまり相関関係にある可能性があるという可能性に取り組みました。

その翌年、アラン・チューリングは最初の一般コンピューティング理論を策定し、コンピューターでは決して解決できない問題が存在することを証明しました。

これら二つのアイデアは、それぞれの分野に革命をもたらしました。一見、互いに無関係に思えたかもしれません。しかし今、画期的な証明によって、これら二つのアイデアが融合され、コンピュータサイエンス、物理学、数学における数多くの未解決問題が解決されました。

この新たな証明は、古典的な1と0ではなく、もつれ合った量子ビット、つまりキュービットを用いて計算する量子コンピュータが、理論的には信じられないほど膨大な数の問題の解答を検証するために使用できることを証明した。エンタングルメントとコンピューティングの関連性は、多くの研究者にとって衝撃的なものであった。

「まったくの驚きだった」とウィーンの量子光学・量子情報研究所で量子物理学を研究するミゲル・ナバスクエス氏は語った。

この証明の共著者たちは、計算問題の解答を検証するアプローチの限界を突き止めようと試みました。このアプローチにはエンタングルメント（量子もつれ）が関わっています。この限界を発見したことで、研究者たちはほぼ副産物的に、他の2つの疑問も解決することができました。1つは物理学におけるツィレルソンの問題、つまりエンタングルメントを数学的にモデル化する方法に関する問題、もう1つは純粋数学におけるコンヌ埋め込み予想と呼ばれる関連問題です。

結局、結果はドミノ倒しのように連鎖しました。

「これらのアイデアはすべて同じ時期に生まれました。このように劇的な形で再び結びつくのは素晴らしいことです」と、トロント大学のヘンリー・ユエン氏（シドニー工科大学のジェンフェン・ジ氏、カリフォルニア工科大学のアナンド・ナタラジャン氏とトーマス・ヴィディック氏、テキサス大学オースティン校のジョン・ライト氏とともに、この証明の著者である。5人の研究者はいずれもコンピューター科学者である。

決定不可能な問題

チューリングは、コンピュータが実際に存在する以前から、計算について考えるための基本的な枠組みを定義しました。それとほぼ同時に、彼はコンピュータが解決できないことが証明されている問題が存在することを示しました。それは、プログラムが停止するかどうかという問題です。

通常、コンピュータプログラムは入力を受け取り、出力を生成します。しかし、時には無限ループに陥り、永遠に空回りしてしまうことがあります。自宅でそのような状況に陥ると、対処法はただ一つしかありません。

「プログラムを手動で強制終了する必要があります。ただ切断するだけです」とユエン氏は言った。

チューリングは、コンピュータプログラムが停止するか永久に実行されるかを判断できる万能アルゴリズムは存在しないことを証明しました。それを知るには、実際にプログラムを実行する必要があります。

「100万年も待ってもプログラムは止まらない。200万年待てば済むのだろうか？予測のしようがない」と、ウォータールー大学の数学者ウィリアム・スロフストラ氏は述べた。

技術的に言えば、チューリングはこの停止問題は決定不可能であり、想像し得る最も強力なコンピュータでも解決できないことを証明しました。

チューリングの後、コンピュータ科学者は他の問題を難易度によって分類し始めました。より難しい問題は、より多くの計算リソース、つまりより多くの実行時間とメモリを必要とします。これが計算複雑性の研究です。

結局のところ、すべての問題には 2 つの大きな疑問が存在します。「解決するのはどれほど難しいか？」と「答えが正しいことを確認するのはどれほど難しいか？」

検証のために尋問する

問題が比較的単純な場合は、自分で答えを確認できます。しかし、問題が複雑になると、答えを確認することさえ大変な作業になることがあります。しかし、1985年にコンピュータ科学者たちは、自分で確認できなくても、答えが正しいという確信を持つことが可能であることに気づきました。

この方法は警察の尋問の論理に従っています。

容疑者が手の込んだ話をした場合、細部まで確認するために外に出るのは難しいかもしれません。しかし、適切な質問をすることで、容疑者の嘘を見破ったり、話が真実であると確信したりすることができます。

コンピュータサイエンスの用語で言えば、質問の対象となる2つの当事者は、問題の解決策を提案する高性能なコンピュータ（証明者）と、証明者に質問をして答えが正しいかどうかを判断しようとする、性能の低いコンピュータです。この2つ目のコンピュータは検証者と呼ばれます。

簡単な例を挙げましょう。あなたが色覚異常で、別の人（証明者）が2つのビー玉の色が違うと主張したとします。この主張を自分で検証することはできませんが、巧みな尋問によって真偽を判断することは可能です。

2つのビー玉を背中に隠して混ぜます。そして、証明者にどちらがどちらかを答えてもらいます。もし2つのビー玉が本当に違う色であれば、証明者は毎回正しく答えるはずです。もし2つのビー玉が実際には同じ色、つまり見た目が同じであれば、証明者は半分の確率で間違った答えを出します。

「半分以上の確率で成功しているのを見たら、その色は違うと確信できる」とヴィディック氏は語った。

証明者に質問することで、自分だけで行うよりも広範囲の問題に対する解決策を検証できます。

1988年、コンピュータ科学者たちは、2人の証明者が同じ問題に対して解法を提案した場合に何が起こるかを検討しました。結局のところ、尋問する容疑者が2人いれば、犯罪を解決したり、解法を検証したりするのがさらに容易になります。なぜなら、2人を互いに対戦させることができるからです。

「検証者の力が大きくなります。尋問し、関連する質問をし、答えを照合するのです」とヴィディック氏は述べた。容疑者が真実を語っている場合、彼らの回答はほとんどの場合一致するはずだ。もし嘘をついている場合、回答は矛盾することが多くなる。

同様に、研究者たちは、2 人の証明者に個別に回答を問い合わせることで、問い合わせる証明者が 1 人だけの場合よりも、さらに多くの種類の問題に対する解決策を迅速に検証できることを示しました。

計算複雑性は完全に理論的なもののように思えるかもしれませんが、現実世界とも密接に関連しています。コンピュータが問題を解決し検証するために必要なリソース、つまり時間とメモリは、根本的に物理的なものです。そのため、物理学における新たな発見は、計算複雑性を変化させる可能性があります。

「古典物理学ではなく量子物理学のような異なる物理学を選択すれば、そこから異なる複雑性理論が得られる」とナタラジャン氏は語った。

この新たな証明は、21 世紀のコンピューター科学者が、20 世紀物理学の最も奇妙な概念の 1 つである「エンタングルメント」に取り組んだ結果である。

コンネス埋め込み予想

二つの粒子がエンタングルメント（量子もつれ）しているとき、それらは実際には互いに影響を与えません。つまり、因果関係がないということです。アインシュタインと共著者たちは、1935年の論文でこの考えを詳しく説明しました。その後、物理学者と数学者は、エンタングルメントの真の意味を数学的に記述する方法を見つけ出そうとしました。

しかし、その取り組みは少々混乱したものでした。科学者たちは量子もつれについて2つの異なる数学モデルを考案しましたが、それらが互いに同等であるかどうかは明確ではありませんでした。

この潜在的な不協和音は、遠回しに言えば、純粋数学における「コンヌ埋め込み予想」と呼ばれる重要な問題を生み出しました。そして最終的に、この不協和音は5人のコンピューター科学者が新たな証明に利用する亀裂ともなりました。

エンタングルメントをモデル化する最初の方法は、粒子を空間的に互いに孤立した状態と考えることでした。例えば、一方は地球上に、もう一方は火星上にいるとします。両者の間の距離が因果関係を阻害するのです。これはテンソル積モデルと呼ばれます。

しかし、状況によっては、二つのものが因果的に独立しているかどうかが完全には明らかではない場合があります。そこで数学者たちは、因果的独立性を記述する、より一般的な第二の方法を考案しました。

2つの演算を実行する順序が結果に影響を与えない場合、演算は「交換可能」です。つまり、3 x 2は2 x 3と同じです。この2番目のモデルでは、粒子の特性が相関している場合に粒子はエンタングルメント状態にありますが、測定を実行する順序は重要ではありません。粒子Aを測定して粒子Bの運動量を予測することも、その逆も可能です。どちらの方法でも同じ答えが得られます。これは、エンタングルメントの交換演算子モデルと呼ばれます。

どちらのエンタングルメントの記述も、行列と呼ばれる行と列に整理された数値の配列を使用します。テンソル積モデルでは、有限数の行と列を持つ行列を使用します。可換演算子モデルでは、無限数の行と列を持つ行列のように機能する、より一般的なオブジェクトを使用します。

時が経つにつれ、数学者たちはこれらの行列を、物理世界との繋がりを全く切り離した、それ自体が興味深い対象として研究するようになりました。この研究の一環として、1976年にアラン・コンヌという数学者は、多くの無限次元行列を有限次元行列で近似できるはずだという予想を立てました。これはコンヌ埋め込み予想の含意の一つです。

その後の10年間、ボリス・ツィレルソンという物理学者が、この問題を再び物理学の枠組みに組み込む新たなバージョンを提唱しました。ツィレルソンは、テンソル積と可換作用素を用いたエンタングルメントのモデルはほぼ同義であると予想しました。これは理にかなっています。なぜなら、これらは理論的には同じ物理現象を記述する2つの異なる方法だからです。その後の研究で、行列とそれを用いる物理モデルとの関連性から、コンヌ埋め込み予想とツィレルソンの問題は互いに関連していることが示されました。つまり、どちらかを解けば、もう片方も解けるということです。

しかし、両方の問題の解決策は結局、まったく別のところからもたらされることになりました。

ゲームショーの物理学

1960年代、ジョン・ベルという物理学者は、エンタングルメントが単なる理論上の概念ではなく、現実の物理現象であるかどうかを判断するためのテストを考案しました。このテストは一種のゲームで構成されており、その結果によって、通常の非量子物理学を超えた何かが作用しているかどうかが明らかになります。

コンピューター科学者は後に、エンタングルメントに関するこのテストが、非常に複雑な問題に対する答えを検証するためのツールとしても使用できることに気付きました。

まず、ゲームの仕組みを理解するために、アリスとボブという2人のプレイヤーと3×3のマス目を想像してみましょう。審判がアリスに1行を割り当て、各マスに0か1を記入して、数字の合計が奇数になるように指示します。ボブは1列を受け取り、合計が偶数になるように記入します。アリスの行とボブの列が重なる場所に同じ数字を入れれば勝ちです。2人は意思疎通ができません。

通常の状況下では、勝率はせいぜい89%です。しかし、量子の状況下では、さらに高い勝率が得られます。

アリスとボブが、エンタングルされた2つの粒子を分割したと想像してください。2人はそれぞれの粒子を測定し、その結果に基づいて、それぞれのマスに1か0を書き込むかを決定します。粒子はエンタングルされているため、測定結果は相関し、つまり答えも相関します。つまり、2人は100%の確率でゲームに勝つことができるのです。

したがって、2人のプレイヤーが予想外に高い確率でゲームに勝っているのを見たら、彼らは古典物理学以外の何かを有利に利用していると結論付けることができます。このようなベル型の実験は、プレイヤー間の距離にちなんで「非局所」ゲームと呼ばれています。物理学者は実際に実験室でこれを行っています。

「人々は何年にもわたって実験を行っており、この不気味なものが本当に存在することを証明している」とユエン氏は語った。

他のゲームを分析する場合と同様に、プレイヤーが最善を尽くした場合、非局所的なゲームでどれくらいの頻度で勝てるかを知りたい場合があります。例えば、ソリティアでは、完璧にプレイした人がどれくらいの頻度で勝つ可能性があるかを計算できます。

しかし2016年、ウィリアム・スロフストラは、あらゆる非局所的ゲームにおいて正確な最大勝率を計算する一般的なアルゴリズムは存在しないことを証明しました。そこで研究者たちは、「少なくとも最大勝率を概算することはできるだろうか？」と考えました。

コンピュータ科学者たちは、エンタングルメントを記述する2つのモデルを用いて、ある答えに迫りました。テンソル積モデルを用いるアルゴリズムは、すべての非局所ゲームにおける近似的な最大勝利確率の下限、つまり最小値を設定します。一方、可換演算子モデルを用いる別のアルゴリズムは、上限を設定します。

これらのアルゴリズムは、実行時間が長くなるほど、より正確な答えを出します。もしツィレルソンの予測が正しく、2つのモデルが実際に同等であれば、下限と上限は徐々に接近し、おおよその最大勝率が1つの値に絞られるはずです。

しかし、ツィレルソンの予測が外れ、2つのモデルが同等でない場合、「天井と底は永遠に分断されたままになる」とユエン氏は述べた。非局所的な試合では、勝率のおおよその計算さえ不可能になるだろう。

新たな研究において、5人の研究者は、天井と床が収束するかどうか、およびツィレルソンの問題が真か偽かというこの疑問を利用して、計算問題に対する答えをいつ検証できるかという別の疑問を解決した。

絡み合った援助

2000 年代初頭、コンピューター科学者たちは、「もつれ合った粒子を共有する 2 つの証明器を調べると、検証できる問題の範囲がどのように変化するのか」という疑問を抱き始めました。

多くの人は、エンタングルメントは検証に不利に働くと考えていた。結局のところ、二人の容疑者が何らかの形で回答を一致させる手段を持っていれば、一貫した嘘をつきやすくなるからだ。

しかし、ここ数年で、コンピューター科学者たちはその逆が真実であることに気付きました。つまり、もつれ合った粒子を共有する証明者を調べることで、もつれがない場合よりもはるかに多くの種類の問題を検証できるのです。

「エンタングルメントとは、相手が嘘をついたり不正行為をしたりするのに役立ちそうな相関関係を生み出す手段です」とヴィディック氏は述べた。「しかし実際には、それを有利に利用することもできるのです。」

その方法を理解するには、まず、このインタラクティブな手順を通じて解決方法を検証できる問題の、ほぼ異世界的な規模を把握する必要があります。

グラフを想像してみてください。点（頂点）の集合が線（辺）で結ばれています。辺で結ばれた頂点が同じ色にならないように、頂点を3色で塗り分けることができるかどうか知りたいと思うかもしれません。もしそれができるなら、そのグラフは「3色塗り可能」です。

エンタングルされた証明者のペアに非常に大きなグラフを渡し、彼らがそれを 3 色にできると報告した場合、あなたは疑問に思うでしょう: その答えを検証する方法はあるのでしょうか?

非常に大きなグラフの場合、作業を直接確認することは不可能です。そこで、代わりに、各証明者に、接続された2つの頂点のうち1つの色を答えてもらうように依頼します。もし証明者がそれぞれ異なる色を答え、しかも毎回同じ答えを返すようであれば、3色塗り分けが実際に機能していることに確信を持てるでしょう。

しかし、グラフが非常に大きくなると、この調査戦略でさえも機能しなくなります。辺と頂点の数は宇宙の原子の数よりも多くなります。具体的な質問（「XYZ頂点の色を教えてください」）を述べるというタスクでさえ、検証者であるあなたの手に負えません。特定の頂点に名前を付けるために必要なデータ量は、あなたの作業記憶に保持できる量を超えているのです。

しかし、エンタングルメントにより、証明者が自ら質問を思いつくことが可能になります。

「検証者は質問を計算する必要はありません。検証者は証明者に質問を計算するよう強制するのです」とライト氏は述べた。

検証者は証明者に、接続された頂点の色を報告してもらいます。頂点が接続されていない場合、質問への回答はグラフが3色であるかどうかについて何も示しません。言い換えれば、検証者は証明者に相関性のある質問をしてもらいたいと思っています。つまり、一方の証明者は頂点ABCについて質問し、もう一方の証明者は頂点XYZについて質問します。どちらの証明者も、相手がどの頂点について考えているかは知りませんが、2つの頂点が互いに接続されていることを期待します。（アリスとボブが、相手がどの行または列について質問されているかは知らないにもかかわらず、同じマスに同じ数字を記入することを望むのと同じです。）

もし二人の証明者がこれらの問題を完全に独力で考え出していたとしたら、検証者が彼らの答えを検証できるように、接続された、あるいは相関のある頂点を選択するよう強制する方法はないでしょう。しかし、まさにそのような相関こそが、エンタングルメントによって可能になるのです。

「エンタングルメントを利用して、ほぼすべての処理を証明者に委ねます。証明者に自ら質問を選択させるのです」とヴィディック氏は述べた。

この手順の最後に、証明者はそれぞれ色を報告します。検証者はそれらが同じかどうかを確認します。グラフが本当に3色に塗り分け可能な場合、証明者は決して同じ色を報告することはありません。

「三色化が存在するなら、証明者はそれを存在を証明できるだろう」とユエン氏は語った。

結局のところ、この検証手順は非局所ゲームのもう一つの例です。証明者は、自分の解が正しいと納得させることができれば「勝利」します。

2012年、ヴィディック氏と伊藤剛氏は、エンタングルド証明器を用いて様々な非局所ゲームをプレイすることで、2台の古典コンピュータで検証できる問題と少なくとも同数の問題の解答を検証できることを証明しました。つまり、エンタングルド証明器の使用は検証に悪影響を与えないということです。そして昨年、ナタラジャン氏とライト氏は、エンタングルド証明器との相互作用によって検証可能な問題の種類が実際に拡大することを証明しました。

しかし、コンピュータ科学者たちは、この方法で検証できる問題の全容を把握していませんでした。これまでは。

連鎖的な結果

新しい論文では、5人のコンピューター科学者が、エンタングルド証明者を調査することで、停止問題を含む解決不可能な問題に対する答えを検証できることを証明している。

「このタイプのモデルの検証能力は本当に驚くべきものです」とユエン氏は語った。

しかし、停止問題は解決できない。そして、その事実こそが、最終的な証明を始動させるきっかけとなるのだ。

エンタングルされた証明者2人にプログラムを渡すところを想像してみてください。そして、プログラムが停止するかどうかを尋ねます。あなたは、ある種の非局所ゲームを通して彼らの答えを検証する準備ができています。証明者は質問を生成し、答えの整合性に基づいて「勝利」を収めます。

プログラムが実際に停止した場合、証明者はこのゲームに100%の確率で勝てるはずです。これは、グラフが実際に3色に着色可能な場合、エンタングルド証明者は接続された2つの頂点に同じ色を報告しないはずであるのと同じです。プログラムが停止しない場合、証明者は偶然によってのみ、つまり50%の確率で勝つはずです。

つまり、この非局所ゲームの特定のインスタンスにおける最大勝利確率のおおよその値を求めるように求められた場合、まず停止問題を解く必要があります。そして、停止問題を解くことは不可能です。つまり、非局所ゲームにおける最大勝利確率のおおよその値を計算することは、停止問題と同様に決定不可能なのです。

これは、ツィレルソンの問題に対する答えが「ノー」であることを意味します。つまり、2つのエンタングルメントモデルは同等ではないということです。もし同等であれば、床と天井をつまんで最大勝率を概算できるからです。

「そのようなアルゴリズムは存在し得ないので、2つのモデルは異なるはずだ」とマドリード・コンプルテンセ大学のダビド・ペレス＝ガルシア氏は語った。

この新しい論文は、量子もつれ証明器との相互作用を通して検証可能な問題群（MIP*）が、停止問題よりも困難ではない問題群（RE）と全く同じであることを証明しています。論文のタイトルは簡潔に「MIP* = RE」と表現しています。

2 つの複雑性クラスが等しいことを証明する過程で、コンピューター科学者は、ツィレルソンの問題が誤りであることを証明しました。これは、以前の研究により、コンヌの埋め込み予想も誤りであることを意味していました。

これらの分野の研究者にとって、このような大きな問題に対する答えが、一見無関係に見えるコンピューターサイエンスの証明から出てくるというのは驚くべきことだった。

「MIP* = REと書かれた論文を見ても、自分の研究とは何の関係もないと思うでしょう」と、ツィレルソンの問題とコンヌの埋め込み予想を結びつけた過去の研究の共著者であるナバスクエス氏は述べた。「私にとっては、全くの驚きでした。」

量子物理学者と数学者は、この証明を理解し始めたばかりです。この新しい研究以前、数学者たちは、無限次元行列を近似する代わりに、巨大な有限次元行列を用いることでうまく近似できるのではないかと考えていました。しかし今、コンヌ埋め込み予想が誤りであるために、それが不可能であることが分かっています。

「彼らの結果はそれが不可能であることを示唆している」とスロフストラ氏は語った。

コンピューター科学者自身はコンヌの埋め込み予想に答えることを目的としていなかったため、結果的に彼らが解決した問題の意味を説明できる最適な立場にはいません。

「私は数学者ではありません。コンヌ埋め込み予想の元々の定式化をよく理解していません」とナタラジャン氏は述べた。

ヴィディック氏と共著者たちは、数学者たちがこの新しい結果をそれぞれの分野の言語に翻訳してくれることを期待している。証明を発表したブログ記事の中で、ヴィディック氏は「純粋に数学的な帰結を得るために、最終的には複雑性理論は必要なくなるだろうと確信している」と述べている。

しかし、他の研究者たちが証明を進めるにつれ、そのきっかけとなった研究の流れは行き詰まりつつある。30年以上もの間、コンピュータ科学者たちはインタラクティブ検証がどれほどの成果をもたらすのかを探ってきた。そして今、彼らはその答えを、シンプルなタイトルとチューリングを彷彿とさせる長文の論文という形で突きつけられている。

「2つの量子もつれ証明器を用いた検証手順がどれほど強力になるかを探る研究が長らく続いてきました」とナタラジャン氏は述べた。「今、私たちはそれがどれほど強力であるかを知りました。その物語はこれで終わりです。」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

WIREDのその他の素晴らしい記事