18年間の量子推測、わずか3日で書かれた証明と2019年に崩壊した証明との違い

アーロンソン教授は「おめでとう」と述べ、その功績を称えました。しかし数日後、事態は急変しました。パータ・イバニシビリ（Paata Ivanishvili）という研究者が、論文の核心的部分である「補題5.3（Lemma 5.3）」において致命的な論理エラーを発見し、論文は最終的に撤回されました。アーロンソン教授は「残念なことに撤回された（retracted）」とし、「歴史的な理由からこの文章を残しておく」と記しました。

PSIの研究システムは実行開始からわずか3日で論理を完成させ、作成されたすべてのステップは『Lean』という証明検証言語により、コンピュータが直接確認しました。60ページに及ぶ論文と検証コードは、GitHubを通じて公開されています ¹²。

なぜ今回、3日で書き上げられた証明は2019年のように覆される可能性が低いのでしょうか？ 鍵は「検証方式」の構造的な違いにあります。過去には、人間が論理を読み判断する過程で微細な欠陥が見逃されることがありましたが、Leanによる検証は、論理が作成された直後にコンピュータが段階的にエラーを検出する方式を採用したためです。ただし、今回の証明が学界の伝統的な査読を完全に通過したか、またAIがどのような数学的洞察を用いて解を見つけたのかについては、公開されている資料からは明確に確認されていません。

量子コンピュータの利点は「構造」に宿る

アーロンソン-アンバニスの推測を理解するには、量子コンピュータがどの時点で古典コンピュータより圧倒的に高速なのかを考慮する必要があります。量子コンピュータは素因数分解などの特定の課題において、指数的な高速化を実現します。しかし、この高速化がすべての課題に適用されるわけではありません。アーロンソン教授は以前から「入力値が完全にランダムである場合、量子コンピュータは本当に古典コンピュータより速いのか？」という疑問を抱いていました。

アーロンソン教授の論理は以下の通りです。量子アルゴリズムがT回の質問で入力にアクセスする場合、1998年のビールズ（Beals）らの結果に基づき、その結果は次数が2T以下の多項式として表現されます。もしこの多項式において影響度が大きい変数が必ず存在する場合、古典コンピュータでもその変数にのみ集中して質問することで、多項式時間の質問数で量子アルゴリズムを模倣できます。すなわち、量子コンピュータの真の利点は、入力データ自体に「隠された構造」がある場合にのみ生じる、というのがこの考えでした。この考えを数学的に証明するため、アーロンソン教授とアンドリス・アンバニ（Andris Ambainis）は2008年頃にこの推測を提案し、2011年の論文『量子高速化には構造が必要である（The Need for Structure in Quantum Speedups）』において正式に定式化されました ³。

この推測は、$n$個の変数を持つ多項式 $p$ の性質を扱います。ここで、2つの核心的概念を容易に理解する必要があります。

1. 分散（Variance）：多項式 $p$ が入力値に応じて値がどの程度広範囲に分布しているかを表します。値が0と1の間を行き来し大きく変動する場合、分散が高いと見なします。
2. 影響度（Influence）：特定の一つの変数を0から1に（またはその逆に）変更した際、多項式 $p$ の値が平均的にどの程度大きく変化するかを表します。

推測の内容は、「多項式の値が広範囲に分布している場合（高い分散）、その変化の相当部分を責任を持つ単一の変数が必ず存在する（高い影響度）」というものです。数学的には、ある変数 $i$ の影響度（$Inf_i$）が、分散（$Var$）と次数（$d$）で表現可能な一定水準以上でなければならないと述べています。

これが量子コンピュータと関連する理由は、1998年のビールズ（Beals）らの研究結果にあります。量子コンピュータが入力値に対して $T$ 回質問して得られる結果は、「次数の低い多項式」で表現できます。もしアーロンソン-アンバニスの推測が真実であれば、古典コンピュータも「影響度の大きい変数」のみを集中的に質問し多項式を解析することで、量子コンピュータの挙動を模倣できます。結論として、量子コンピュータが古典コンピュータよりも指数的に高速になるためには、入力データに特定の数学的構造が不可欠であるという事実が証明されることになります ³。

2019年、一行の論理が崩壊の始まりだった

アーロンソン教授は19ページに及ぶ論文を精読し、「素晴らしい（It's great!）」と肯定的に評価しました。しかしアーロンソン教授が精読を終えた後の11月20日、ケラーとクラインは、パータ・イバニシビリが発見した補題5.3のエラーにより論文を撤回するとの連絡を入れてきました ³。

問題は、このような微細な論理の欠陥が発見されにくい点にあります。人間が複雑な数学論文を読む際には、一文一文の妥当性を「信じて」見逃すことが多くあります。アーロンソン教授でさえ「ノイズ演算子や超縮小性（hypercontractivity）などの内容は信じて見逃した」と振り返っています ³。特にケラー-クラインの証明は、特定の変数の影響を分析し関数を単純化する複雑な過程を経ていましたが、この過程において特定の補題が論理の崩壊を引き起こす弱点となっていました。

最終的に2019年の撤回により期待されていた証明は再び頓挫し、この推測はその後もしばらく未解決のまま残りました。

Lean（リーン）による検証が作る新しい規則

2026年の証明が2019年の失敗を繰り返さないと期待される最大の理由は、「Lean」の使用です。Leanは、数学の論文をコンピュータが理解できるコードに翻訳し、論理のすべてのステップを機械的に検証するツールです。人間のレビュアーは論文を読みながら「大まかに正しいだろう」と判断できますが、Leanはたった一つの論理規則違反も許しません。

PSIは2026年9月に設立されたAI物理学研究企業で、物理学の問題を仮説ツリーに分解し並列検証する「Emmy」プラットフォームを使用しています ⁴。過去にこの企業が実施したプロジェクト報告書では、「反証的監査（adversarial audit）」を実施することを強調していました。今回の証明プロセスでは、AIシステムが論理を作成すると、Leanがこれを段階的に確認する構造を経ていました ¹²。

以下の表は、2019年と2026年の証明試行の主な違いを比較したものです。

項目	2019年（ケラー-クライン）	2026年（PSI）
証明主体	人間の数学者	AIシステム（非公開のAnthropicモデルに基づく）
所要期間	約11年間にわたり未解決だった推測への試行	実行後3日間で導出
検証方式	人間のレビュアーの判断への依存	Lean言語による段階的な機械検証
結果	補題のエラーにより撤回	機械検証完了（査読の進行状況は非公開）

資料出典：¹²³

機械が埋めた論理の隙間、残された課題

アーロンソン-アンバニスの推測は、量子コンピュータの計算能力の本質的な限界を解明する重要な鍵でした。2008年に提示されて以来18年間未解決だったこの推測において、2019年の一つの補題のエラーが証明の試みを白紙に戻したことを考えると、わずか3日で機械検証まで完了した今回の証明は意義深いものです。

PSIのAIは、非公開のAnthropicモデルを並列運用して論理を構成し、その結果はLeanによる厳格な段階的検証を通過しました。多項式の分散と影響度を比較する複雑な数学的直観がコンピュータコードに変換され、論理エラーがないことが確認されたのです。

しかし、この証明が学界全体の合意であるかどうかは、まだ断定するのが難しい状況です。論文の内容と解釈について伝統的な査読がどのように進行するか、そしてAIが具体的にどのような数学的戦略でこの解を見出したのかは、公開資料の外にある領域です。重要なのは、機械検証という新しい基準が「論理の隙間」を埋め、過去の失敗を繰り返さないための強力なツールとなったという事実です。

参考文献

1. 🚨 18년 동안 풀리지 않던 양자컴퓨팅 난제를 AI가 증명했습니다. 물리학 AI 스타트업 PSI가 비공개 앤트로픽 모델로 돌린 연구 시스템이 실행 사흘째에 애런슨-암바이니스 추측의 증명을 찾았고, Lean으로 모든 단계를 기계 검증까지 마쳤습니다 🧵 · threads.com
   ↩
2. 1/ 물리학 AI 스타트업 Physical Superintelligence(PSI)가 11월 6일 애런슨-암바이니스 추측의 증명을 공개했습니다. 양자컴퓨터가 일반 컴퓨터보다 기하급수적으로 빨라질 수 있는 조건을 다룬 추측으로, 스콧 애런슨이 2008년 강연에서 처음 꺼낸 뒤 18년 동안 열려 있었는데요. PSI 연구원… · threads.com
   ↩
3. The Aaronson-Ambainis Conjecture (2008-2019) · scottaaronson.blog
   ↩
4. Physical Superintelligence Menggalang Pendanaan Awal $58 Juta · unite.ai
   ↩