Anthropicの非公開AIモデルを使って18年間未解決だった量子コンピューターの難問が証明される

AI物理学スタートアップのPhysical Superintelligence(PSI)が2026年11月6日、2008年から未解決だった量子コンピューティングの難問「アーロンソン＝アンバイニス予想」の証明に成功したと発表しました。証明にはAnthropicの非公開AIモデルを組み込んだ研究システムが使われており、数学的な証明をコンピューターで検証する「Lean」による確認も完了しているとのことです。

A proof of the Aaronson-Ambainis conjecture · PSI
https://psi.inc/research/aaronson-ambainis/

量子コンピューターは量子力学の性質を利用することで、従来のコンピューターでは膨大な時間がかかる計算を高速に処理できると期待されています。例えば1994年に数学者のピーター・ショア氏が考案した「ショアのアルゴリズム」は、大きな整数の素因数分解を従来知られていた方法よりも大幅に高速化できる量子アルゴリズムです。

ただし、量子コンピューターが圧倒的な性能を発揮するためには、計算対象となる問題に特定の規則性や構造が必要なのかという疑問が残されていました。ショアのアルゴリズムも、数値に隠された周期的な規則性を利用しています。

2008年に計算機科学者のスコット・アーロンソン氏とアンドリス・アンバイニス氏が提唱した「アーロンソン＝アンバイニス予想」は、量子コンピューターの高速化に規則性が必要かどうかを数学的に解明するための予想です。

アーロンソン＝アンバイニス予想が正しければ、ランダムな入力の大部分について、量子コンピューターが従来のコンピューターより指数関数的に少ないデータ参照回数で計算を終えることはできないと示されます。つまり、量子コンピューターによる極めて大きな高速化には、問題に隠された特別な規則性が必要になるというわけです。

PSIはアーロンソン＝アンバイニス予想を解決するため、独自に開発したAI研究システムを使用しました。研究システムにはAnthropicが開発した非公開AIモデルが組み込まれており、PSIの研究者が問題を設定し、独自の計算環境で実行したとのこと。

PSIによると、AI研究システムは実行開始から3日目にアーロンソン＝アンバイニス予想の完全な証明を発見しました。さらに関連する数学的問題の研究を進める過程で証明を2回改良し、最終的な証明も完成させています。

数学の証明では結論が正しいかどうかに加え、結論に至るまでの論理に誤りがないかを確認する必要があります。特にAIが作成した複雑な証明については、もっともらしい説明に誤りが含まれている可能性があるため、厳密な検証が重要になります。

そこでPSIは定理証明支援システム「Lean 4」を使い、証明をコンピューターが確認できる形式に変換しました。PSIが公開した資料によると、Leanによる証明は未完成部分や新たな公理の追加なしで完成しており、独立した2種類の検証プログラムでも確認済みとのこと。GitHubには論文のほか、Leanのソースコードや検証手順、検証結果の記録も公開されています。

GitHub - physical-superintelligence/aaronson-ambainis
https://github.com/physical-superintelligence/aaronson-ambainis

研究成果については専門家からも反応が寄せられています。量子計算を専門とする研究者のヘンリー・ユエン氏は、量子コンピューターによる指数関数的な高速化に規則性が必要かどうかという美しい問題が解決されたと紹介。

Ah, another beautiful question in quantum complexity theory solved! This one is due to Scott Aaronson and @AAmbainis, about the necessity of structure in a problem for exponential quantum advantage. This question inspired a lot of research and we collectively learned a lot about… https://t.co/jkqOJBBBpQ

— Henry Yuen (@henryquantum) 2026年11月6日

また、数学者のパータ・イヴァニシュヴィリ氏は「証明が正しければ大きな成果になる」と評価しました。

Congratulations -- this would be a major result if it holds.

I’ve spent a fair amount of time on this problem myself. A positive resolution essentially means quantum algorithms can be classically simulated in polynomial time on most inputs on big class of problems.

PS. I… https://t.co/16skqPuADp

— Paata Ivanisvili (@PI010101) 2026年11月6日

PSIによると、2026年8月にアーロンソン＝アンバイニス予想の特殊な場合を解決したスタンフォード大学の研究者らも今回の証明を確認しており、専門家向けに内容を簡潔にまとめた解説の執筆を進めているとのこと。PSIは今回の成果について「量子コンピューティングにはまだ多くの謎が残されていますが、謎が1つ減りました」と述べています。