← ブログに戻る
Ai読了目安 15 分

18年来の量子予想が3日で解決した。証明には検証器が付いていた。

公開日 2026年11月7日
18年来の量子予想が3日で解決した。証明には検証器が付いていた。

11月6日、Physical Superintelligence(PSI)は、社内研究システムがAaronson-Ambainis予想を証明したと発表した。完全な論証を生み出すのに、実行は3日かかった。計算機にすべてのステップを検証させる証明アシスタント、Leanがそれを受け入れた。システムはその後、関連する問題にも取り組み、結果を2度強化し、Leanは最終版も受け入れた。

PSIは人間が読める論文と、Apache 2.0の下での完全なLean 4形式化の両方を公開した。リポジトリには、開発に証明のプレースホルダーも追加された公理も含まれず、4つの主要定理はLeanのカーネルと、同じ型チェッカーの独立実装であるlean4leanを通して再実行されたと記されている。Leanとnanodaの両方のカーネルを使うコンパレータは最終版を受け入れた。別のマシンでは、同じコンパレータが1つの正しいテスト用の解を受け入れ、意図的に誤った4つを却下した。

私が何度も立ち返るのは、この対照テストの部分だ。主張とレシートを分けるのは、これである。

この予想が実際に述べていること

有名な量子高速化のほとんどは構造に依存している。1994年のショアの因数分解アルゴリズムが機能するのは、入力に繰り返し周期が隠れているからだ。一様ランダムな入力についてのイエス/ノー質問に量子コンピュータが答えるとなると、その構造は失われる。ここに未解決問題があった。量子マシンはそれでも指数関数的に高速になり得るのか。

AaronsonとAmbainisはこの問いを多項式についての命題に変えた。クエリモデルでは、アルゴリズムが入力を何回読むかを数える。T回のクエリの後、量子アルゴリズムがイエスと答える確率は、値が0と1の間に収まる、次数高々2Tの多項式として書ける。そのアルゴリズムを古典的にシミュレートするには、指数関数的な数の入力ビットを読まずに多項式を推定する必要がある。

この予想によれば、ほぼ定数でない有界な低次多項式には、影響度の高い座標が少なくとも1つある。その1ビットを反転させると、多項式の値は平均して意味のある量だけ動かなければならない。これが成り立てば、古典マシンは任意のTクエリ量子アルゴリズムを、ほとんどの入力に対してTの多項式回のクエリでシミュレートできる。非構造的な入力での指数的高速化はない。

PSIの証明は明示的な境界を与える。あるビットの影響度は、少なくとも定数かける v の 5/2 乗を d の6乗で割ったもの以上である。ここで v は分散、d は次数で、定数は約0.0025だ。より緩い形では、少なくとも (v/d)^7 である。

その道筋は、Shachar LovettとJiapeng Zhangが描いた計画に従っている。分数証明書とレベル集合に基づくものだ。LovettとZhangは1つの不等式を未解決のまま残し、それを予想として述べていた。PSIのシステムはそれを、入力設定の行列式に基づくペアリングから導かれる新しい全ペア不等式に置き換えた。これは、座標が一致できる数を制限することで、David Reimerの以前のバタフライ補題を越えるものだとPSIは述べている。

何が機械検証され、何がされていないか

この話の報道の多くが間違えるのは、ここだと思う。Leanの証明は強力な成果物だ。しかし結果全体の完全な認証ではない。PSI自身もそう述べている。

機械検証の外側には3つのものがある。Leanのカーネル、コンパイラ、Mathlibの定義、そして検証を行っているハードウェアはすべて信頼基盤の一部だ。文章形式の論文は機械検証されておらず、検証されるのは形式文だけである。そして、その形式文がAaronsonとAmbainisが2008年に印刷した予想と一致することを、人間がまだ確認しなければならない。

PSIはこの最後のステップを可能な限り容易にした。リポジトリは`PrintedConjecture`という単一の定義を、Mathlib以外を何もインポートしないファイルに分離している。だから懐疑的な読者は1つのファイルを開き、元の論文と比較できる。これは検証のためのよく考えられたインターフェース設計であり、著者たちが弱点がどこかを分かっていたことも示している。

暗い木製の机の上で、細い真鍮の定規で平らに押さえられた白い紙。午後の光が一筋差し込んでいる。

監査は内部で行われた。Jim Halversonが証明を監査し、Phiala Shanahanが形式化についてコメントした。2人ともPSIのアドバイザーだ。査読も学術誌への掲載もまだない。2026年8月に特殊ケースを証明したスタンフォード大学の4人の研究者、Guy Blanc、Jordan Docter、Carmen Strassle、Li-Yang Tanは、完全な証明を読み、コメントを送り、より短い解説を準備している。彼らの引用された評価は、それを巨大な成果と呼んでいる。関心を持つ専門家とのやり取りは有用だ。だが査読ではない。

人間の役割が明記されているのは評価できる。MITで物理学とAIを学んだ技術スタッフのDavid Turtureanが研究システムを構築し、問題の範囲を定め、実行し、非公開のAnthropicモデルのインスタンスに初稿をまとめるよう指示し、その草稿をレビューし、論文の正確性に対する責任者として名を連ねている。リポジトリは、数学的命題、初稿、Lean形式化をAIモデルが生成したことを開示している。

この分業は率直に述べておく価値がある。なぜなら、これは普通のことになっていくからだ。人間が問題を選び、責任を負う。モデルが候補となる論証を生む。チェッカーが閉じないものを却下する。出力は、ノートPCと午後の時間があれば誰でも再実行できる主張だ。

なぜモデルよりチェッカーが重要なのか

Anthropicは、この背後にあるモデルをいつ、あるいは出荷するのかを明らかにしていない。その詳細はほとんど枝葉だ。ここで興味深い対象はパイプラインであり、そのパイプラインはベンチマークスコアとは違って再現可能だ。

懐疑的な数学者がこの公開で何をできるか考えてみてほしい。リポジトリをクローンする。`PrintedConjecture`を読む。Leanを実行する。lean4leanを実行する。コンパレータを実行する。公理が追加されていないことを確認する。これらのステップはすべて合格か不合格のどちらかで、失敗の仕方も具体的だ。

代替案と比べてみよう。ラボがグラフと製品ページと、推論能力の改善についての一段落を投稿する。あなたはそれを信じるか、信じないかしかない。

形式検証は魔法ではなく、数学を決着させるものでもない。決着させるのはもっと狭いことだ。特定の形式文が、特定の公理から特定の規則によって導かれるかどうか。その文が正しいものかどうか、公理が正しいものかどうか、結果が重要かどうかは、すべて人間に残る。

PSIはマサチューセッツ州ケンブリッジを拠点とする公益法人(public benefit corporation)で、9月にBreakthrough Energy Venturesが主導した5800万ドルのシードラウンドで公に始動した。自らを、理論家のように推論し、計算物理学者のように検証する仮想物理学者を擁するAIネイティブの物理学ラボと説明している。先月には量子情報理論の長年の問題を5つ解決したと述べ、これは約2週間で2度目の主要発表になる。このペースは、外部の注目に晒された後どれだけが残るかによって、印象的にも警告にもなる。

量子の物語にとって何を意味するか

この結果は境界を鮮明にする。非構造的なランダム入力についてのイエス/ノー質問では、量子マシンは指数的に多くのクエリを節約できない。アルゴリズム設計者は、汎用入力での高速化を探すのではなく、数学や物理学の中に実際の構造がある問題を探すべきだ。

どの応用が実を結ぶかは教えてくれない。クエリモデルは入力の読み取り回数を数えるのであって、データの読み込みや処理の仕事を数えるのではない。したがって、総実行時間や量子コンピュータの商業的価値に一般的な制限を課すものではない。この論文を、量子コンピューティングは死んだことの証拠として引用する人は、論文に書かれていないことを引用している。

もう1つ、これが行わないのは、AIが研究を行うことについての議論を終わらせることだ。内部システムによって生み出され、内部で監査され、周辺文献がすでにアプローチを1つの未解決不等式に絞り込んでいた問題についての単一の結果は、1つのデータ点にすぎない。LovettとZhangには計画があった。Reimerには補題があった。システムはギャップを埋めた。それは実際の仕事であり、同時に数学研究が含むもののほんの一部でもある。

残るステップは、PSIが自分ではできないものだ。分野の誰かが形式文を読み、それがAaronsonとAmbainisの予想であって、それに都合よく似た別物ではないと同意し、公にそう述べなければならない。それまでは、存在するのは有名な主張にごく近い何かの機械検証済み導出と、最後の1マイルを短くするために作られたリポジトリだ。

それは、ほとんどの発表が残すよりもよい立場だ。

関連記事