20年にわたり、計算機科学者たちは一見単純な問いに取り組んできた。量子コンピュータは、古典コンピュータが記述すらできない問題の解を検証できるのか？
答えはイエスであり、その証明は96ページに及ぶ。
4人の研究者チーム（John Bostanci〈サイモンズ研究所／コロンビア大学〉、Jonas Haferkamp〈ルール大学ボーフム〉、Chinmay Nirkhe〈ワシントン大学〉、Mark Zhandry〈スタンフォード大学〉）は、少なくとも1つの計算問題において、量子証明が古典的証明よりも明確に強力であることを証明した。この論文は、理論計算機科学の最前線会議である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氏が初めて提起した問いは、量子バージョンが厳密により強力かどうかであった。
チームはその答えがイエスであることを証明した。量子証拠は機能するが古典的証拠は機能しない「スペクトル的フォレレーション問題」と呼ばれる問題を構築したのである。この問題は一種の鑑識パズルである。2つの測定データセットが与えられたとき、それらが同じ量子オブジェクトから得られたのか、それとも異なる2つのオブジェクトから得られたのかを判断する。量子証拠は2つのデータセット間の関係を直接符号化できるが、古典的証拠は十分な情報を運ぶことができない。
証明は「背理法」と呼ばれる戦略を用いる。研究者らはまず、この問題に対する古典的証明が存在すると仮定した。次に、そのような証明は再利用可能であり、同じ古典的証拠を使って多くの異なるクエリに回答できることを示した。しかし、この再利用可能性によって、証明可能なほど不可能な困難な推測タスクを解くことが可能になると実証した。矛盾は元の仮定が誤りであったことを意味する。古典的証明は存在し得ない。
「考え始めたのは偶然のようなものでした」とZhandry氏はQuanta Magazineに語った。2024年11月の彼の単独研究は問題の半分を解決したが完了できなかった。4人が集まり、9カ月の集中的な作業を経て、「それが本当に私の1年を支配しました。他にはほとんど何もしませんでした」とBostanci氏は語り、完全な証明を完成させた。
第二の独立した証明
注目すべきことに、第二のチームが全く異なる手法を用いて独立に同じ結論に達した。MITのAndrew Huang氏とVinod Vaikuntanathan氏はBostanci氏とともに、2026年2月に第二のオラクル分離（arXiv:2602.09385）を発表した。これは概念的により単純であり、量子アドバイスに関する関連分野であるBQP/qpolyクラスとBQP/polyクラスの間の最初の分離ももたらす。
独創的だが複雑なものと、より単純で拡張性のあるものという2つの独立した証明があることで、結果の確実性が強化される。
オラクルに関する注意点
両方の証明は「オラクル分離」である。つまり、コンピュータが問い合わせ可能だが内部動作を見ることができないブラックボックス関数（オラクル）に対して、QMAとQCMAが異なることを示している。オラクルなしの無条件証明には、複雑性理論における革命的進歩が必要であり、PがPSPACEと等しくないことの証明に相当する。
それでも、オラクル分離は非常に強力な証拠と考えられている。主要な複雑性クラス間の既知の分離はすべて、オラクル結果として始まり、その後精緻化されてきた。この分野の歴史は、2つのクラスがオラクルに対して異なる場合、現実においてもほぼ常に異なることを示している。
「私たちが得たものは、答えがイエスであること、つまり量子証明がより強力であることに対する、これまでで最も強力な証拠です」と研究者らは論文に記している。
重要性
現役の量子コンピュータ物理学者にとって、この結果は日常業務を変えるものではないかもしれない。2つのクラスを分離する問題（スペクトル的フォレレーション問題）は注意深く構築された人工的なものである。しかし、証明で開発された手法、特に問題をボソンで扱う「第二量子化」圧縮オラクル法は、暗号技術や量子アルゴリズム設計への応用が期待される。
この結果は、量子複雑性理論における主要な未解決問題の1つも閉じるものである。この分野は、量子リソースで何が計算でき、何ができないかという根本的な問いを扱う。QMA対QCMA問題に20年間取り組んできた研究者たちにとって、ついに答えが出た。
雅子 訳
情報源
- 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月）.