長年にわたり、コンピュータ科学者たちは一見単純な問いに取り組んできた。それは、「古典コンピュータが記述すらできない問題の解を、量子コンピュータは検証できるのか」というものだ。
答えは「はい」であり、その証明は96ページに及ぶ。
4人の研究者（John Bostanci（Simons Institute / Columbia）、Jonas Haferkamp（Ruhr University Bochum）、Chinmay Nirkhe（University of Washington）、Mark Zhandry（Stanford））からなるチームは、量子証明が少なくとも一つの計算問題において古典証明よりも断然強力であることを証明した。この論文は、理論計算機科学の最高峰会議であるSTOC 2026で最優秀論文賞を受賞した。
「これは美しい結果です」と、この研究には関与していないMITの量子情報理論家Anand Natarajan氏は語る。「そこから生まれる新しいアイデアがたくさんあります。」
証明が実際に示すもの
この問題は、複雑性理論と呼ばれる理論計算機科学の一分野に属する。複雑性理論は、問題を解くために必要なリソースが問題の規模に応じてどのように拡大するかを問う分野である。その中心にあるのが、QMA（Quantum Merlin-Arthur）クラスとQCMA（Quantum-Classical Merlin-Arthur）クラスである。
次のように考えてみよう。学生（Merlin）が教師（Arthur）に対して、ある数学的命題が真であることを納得させようとしている。QMAシナリオでは、Merlinは量子状態（壊れやすい量子ビットの集合）を証拠として提出できる。QCMAシナリオでは、Merlinは古典的なビット列のみを提出できる。2002年にDorit AharonovとTomer Navehによって初めて提起されたこの問題は、量子バージョンが厳密により強力であるかどうかを問うものだった。
チームは、「スペクトル相関問題（spectral forrelation problem）」と呼ばれる問題を構築することで、それが正しいことを証明した。この問題では、量子証人は機能するが、古典証人は機能しない。この問題は一種の鑑識パズルである。すなわち、2組の測定データが与えられたとき、それらが同じ量子オブジェクトから得られたものか、異なる2つのオブジェクトから得られたものかを判定する。量子証人は2つのデータセット間の関係を直接エンコードできるが、古典証人は十分な情報を運ぶことができない。
証明では「背理法」と呼ばれる戦略が使われる。研究者らはまず、この問題に対する古典的な証明が存在すると仮定した。そして、そのような証明は再利用可能であり、同じ古典証人を使って多くの異なる質問に答えられることを示した。しかし、この再利用可能性によって、証明不能な難しい推測タスクを解くことが可能になると彼らは実証した。矛盾が生じるため、元の仮定は誤りであり、古典的な証明は存在しえないことになる。
「たまたまそのことを考え始めたんです」とZhandry氏はQuanta Magazineに語った。彼の2024年11月の単独研究では問題の半分を解いたものの、完成には至らなかった。4人が集まり、9ヶ月にわたる集中作業の末、「その年に完全に支配されました。ほとんど他のことはできませんでした」とBostanci氏が語るように、彼らは完全な証明を完成させた。
第二の独立した証明
注目すべきことに、第二のチームが全く異なる方法を用いて独自に同じ結論に達した。MITのAndrew Huang氏とVinod Vaikuntanathan氏がBostanci氏とともに、2026年2月に第二のオラクル分離（arXiv:2602.09385）を発表した。これは概念的によりシンプルであり、BQP/qpolyとBQP/polyという量子アドバイスに関する関連領域における初の分離ももたらす。
独創的だが複雑なものと、よりシンプルで拡張可能なものという、2つの独立した証明があることで、結果の確実性が強化される。
オラクルに関する注意点
両方の証明は「オラクル分離」である。すなわち、QMAとQCMAが、コンピュータが問い合わせることのできるブラックボックス関数（オラクル）に対して異なることを示しているが、その内部動作は見えない。オラクルなしの無条件証明には、複雑性理論における革命的な進歩が必要であり、PがPSPACEと等しくないことを証明するのに相当する。
それでも、オラクル分離は非常に強力な証拠と考えられている。主要な複雑性クラス間の既知の分離はすべて、オラクル結果として始まり、その後洗練されてきた。この分野の歴史は、2つのクラスがオラクルに対して異なる場合、現実においてもほとんど常に異なることを示している。
「私たちが得たものは、答えがイエスであることのこれまでで最も強力な証拠です。量子証明はより強力なのです」と研究者らは論文で述べている。
なぜ重要か
現役の量子コンピュータ物理学者にとって、この結果が日々の業務を変えることはないかもしれない。2つのクラスを分ける問題（スペクトル相関問題）は注意深く構築された人工的なものである。しかし、証明で開発された手法、特に問題をボソンとして扱う「第二量子化」圧縮オラクル法は、暗号理論や量子アルゴリズム設計への応用が期待されている。
この結果はまた、量子複雑性理論における主要な未解決問題の一つを解決する。量子複雑性理論は、量子リソースで何が計算できて何ができないのかという根本的な問いを投げかける分野である。QMA対QCMA問題に20年にわたって取り組んできた研究者たちにとって、ついに答えが出たのである。
雅子 訳
Sources
- Quanta Magazine: 「Researchers Reveal the Power of ‘Quantum Proofs’」（2026年7月6日）. https://www.quantamagazine.org/researchers-reveal-the-power-of-quantum-proofs-20260706/
- Bostanci, J., Haferkamp, J., Nirkhe, C., Zhandry, M. 「Separating QMA from QCMA with a Classical Oracle.」 arXiv:2511.09551. STOC 2026 Best Paper.
- Bostanci, J., Huang, A., Vaikuntanathan, V. 「Separating Quantum and Classical Advice with Good Codes.」 arXiv:2602.09385（2026年2月）.