AIはアーロンソン＝アンバイニス予想（Aaronson-Ambainis）を証明したのか：これまでに確認されたこと

2026年11月6日、スタートアップのPhysical Superintelligence（PSI）は、アーロンソン＝アンバイニス予想（Aaronson-Ambainis conjecture）の証明を発表しました。およそ2008年から未解決だった多項式についての命題で、ランダム入力に対して量子コンピュータがどこまで速くなれるかを制限するものです。¹この証明が成り立つなら、はい／いいえで答える問題では、入力に特別な構造がない限り、量子コンピュータが節約できる入力の読み取り回数は多項式回にとどまり、指数回にはなりません。PSIは、非公開のAnthropicモデルを動かす研究システムがこの証明を見つけたと述べています。PSIのリポジトリには、証明支援系Leanが形式版を受理したと記録されています。³アンドリス・アンバイニス（Andris Ambainis）とともにこの予想を提起したスコット・アーロンソン（Scott Aaronson）は、11月8日、証明をまだ理解していないが正しいと考えている、と書きました。⁴論文はプレプリントで査読を受けておらず、PSIはモデルの名前を明らかにしていません。

その後の一部の投稿の内容にかかわらず、この結果が成り立っても、ショアの素因数分解アルゴリズムや化学の量子シミュレーションには影響しません。関わるのはある特定の種類の優位性で、アーロンソンによれば、それは存在しないと研究者たちがすでに予想していたものです。

以下では、予想の内容、それが量子高速化を制限する理由、影響が及ばない範囲、PSIの報告内容、Leanによる確認で言えることと言えないこと、証明の作られ方について読者に分かること、そして誰が何に責任を負うのかを順に紹介します。出典はすべて2026年11月9日に確認しました。

アーロンソン＝アンバイニス予想とは何か#

PSI自身のたとえが分かりやすいでしょう。多項式とは、オン・オフのスイッチにつながれたダイヤルです。¹各スイッチは入力の文字列の1ビットです。スイッチの小さなグループは、それぞれ、そのスイッチがすべてオンのときに目盛りに決まった量を加えます。最大のグループのスイッチはd個で、dは多項式の次数です。目盛りの値は、どの設定でも0と1の間に収まることが保証されています。

スイッチの影響度（influence）は、そのスイッチがどれだけ効くかを測るものです。スイッチを反転させ、目盛りの変化を2乗し、すべての設定について平均します。PSIが挙げる4ビットの例は f = 0.1 + 0.5·x4 + 0.2·x1·x2 + 0.1·x3 です。ビット4を反転させると目盛りは常に0.5動くので、影響度は0.25です。ビット3を反転させると0.1動き、影響度は0.01です。ビット1が効くのはビット2がオンのときだけで、影響度は0.02になります。

この予想は、有界で次数の低いダイヤルには必ず効くスイッチがある、と述べています。正確には、目盛りの分散が ε 以上なら、変数がいくつあっても、影響度が ε/d のある固定されたべき以上である変数が存在する、というものです。⁵

分散の条件は必要です。Nビットの平均を考えてみます。次数は1で、値は0と1の間に収まり、どのビットの影響度も 1/N² とごく小さくなります。しかし分散も 1/(4N) とごく小さいので、予想がこの多項式に求めることはわずかです。予想が排除するのは、目盛りの値が大きく振れるのに、どのスイッチもほとんど効かないような多項式です。

今回の発表の前は、一般の有界な多項式について知られていた評価は次数について指数的で、予想が証明されていたのは特別なクラスの多項式についてだけでした。²アーロンソンとアンバイニスは論文の中で、主な根拠は類似の定理だとし、こう書いています。「私たちが尋ねたフーリエ解析の専門家が皆これを確信していたという事実を除けば！」。⁵

PSIは、この評価を具体的な形で主張しています。次数がd以下で値が [0, 1] に収まり、分散が ε 以上の多項式には、影響度が (ε/d)^7 以上の変数がある、というものです。より鋭い形では、約 0.0025 · ε^(5/2) / d^6 が得られるとしています。

いつ提起されたのか？ 報道には2008年とするものと2009年とするものがあり、どちらにも根拠があります。アーロンソンは2019年に「だが2008年ごろ、一見関係のなさそうな予想から解決が導かれることに気づいた」と書き、その投稿の題に2008年から2019年までの年を入れました。⁶新しい論文には「この予想は2008年のアーロンソンの講義にさかのぼる」とあります。²論文としては、2009年11月5日にarXivに投稿され、2014年にTheory of Computingに掲載されました。同誌では予想1.7、arXiv版では予想6です。⁵11月8日、アーロンソンはこれを「アンドリスと私が2009年に提起した」予想と述べています。⁴

なぜ量子高速化を制限することになるのか#

量子アルゴリズムは、クエリの数、つまり入力を何回読むかで測られることがよくあります。1998年、Bealsらは、T回のクエリの後に量子アルゴリズムが「はい」と答える確率が入力ビットの多項式であり、次数は高々2Tで、値は0と1の間に収まることを示しました。⁴これはまさに、予想が述べる種類のダイヤルです。そのため、普通のコンピュータが量子コンピュータをまねる方法が得られます。

論文は指数7を使ってコストを計算しています。割合 δ の入力を除いて、確率を誤差 ε 以内で推定するのに必要な古典クエリは、高々 (4T)^8 · ε^-14 · δ^-8 回です。²Tの大きな多項式ですが、多項式です。PSIはこれを「はい／いいえで答える問題では、文字列に珍しいパターンがない限り、量子コンピュータは指数的に多くの読み取りを節約できない」とまとめています。¹

その背景には、FortnowとRogersが1998年に問うた、より古い問題があります。ランダムオラクルのもとでPとBQPを分離できるか、という問題です。⁴ランダムオラクルとは、大まかに言えば、ランダムなデータの入ったブラックボックスです。アーロンソンとアンバイニスは、2人の予想からここに帰結が生じることを示しました。ランダムオラクルのもとでBQPをAvgPから分離するには、それ自体が大きな未解決問題である P ≠ P^#P を証明する必要がある、というものです。²

何を否定しないのか#

否定しないことは数多くあり、論評が最も早く道を誤ったのはこの点です。11月7日、ワシントン大学のPedro DomingosはXに「量子超越性の夢は死んだ」と投稿しました。¹⁷同じ日、ブリストル大学のAshley Montanaroは、「その含意について、まったく誤った論評がこれほど多いのを見て気が滅入る」と書きました。¹⁶

アーロンソンの答えは、この結果は「ある特定の種類の量子超越性（すなわち、ランダムオラクルのもとでのはい／いいえ問題についてのもの）を排除するが、それはそもそも存在しないと私たちがすでに予想していたものだ」というものです。⁴彼の投稿と各論文は、影響を受けないものを挙げています。

• ショアのアルゴリズム。 素因数分解は関数の周期を見つける問題に帰着し、周期的な入力は、ランダムからこれ以上ないほど遠いものです。アーロンソンは「たとえば、ショアの素因数分解アルゴリズムにはまったく影響しない」と書いています。
• 構造のある問題全般。 サイモンの問題のように、入力に約束（promise）がある場合の指数的高速化は、この予想と矛盾しません。論文の要旨は、この規模の高速化は「入力に関する約束のような構造を必要とする」と述べています。²
• 物理と化学のシミュレーション。 アーロンソンによれば、これらは一般にオラクルアルゴリズムにまったく依存していません。
• はい／いいえで答えない問題。 YamakawaとZhandryは2022年、ランダムオラクルのもとで、量子コンピュータには解けて古典コンピュータには解けないNP探索問題があることを示しました。¹¹2人の要旨には、これが予想と矛盾するようには見えないと記されています。
• 実行時間。 この定理が数えているのは入力の読み取り回数です。全体の仕事量は抑えておらず、上のシミュレーションは、次にどのビットを読むかを決めるのに膨大な労力を費やすかもしれません。

PSIは正確には何を報告したのか#

PSIの記事は「アーロンソン＝アンバイニス予想は、いまや定理である」と始まります。¹これはPSIの主張です。同じ日にarXiv:2611.09773として²投稿された論文とあわせて、PSIの説明は次のとおりです。

研究システムはPSI自身の基盤で動き、非公開のAnthropicモデルのインスタンスを使いました。論文のAI利用の開示によれば、これらのインスタンスは「既存のアイデアを探し、新しいアイデアを提案し、それらのアイデアを組み合わせて試し、ほかのインスタンスの作業とインスタンス間のやり取りを監督する」ために使われました。²PSIは、システムが「実行の3日目に、予想の完全な証明を得ていた」と述べています。論文の付録Aによれば、この証明の指数はより弱く、最終版の7に対して22でした。その後、インスタンスが関連する未解決問題に取り組むよう求められてから、指数は11、さらに7へと改善され、各段階はLeanで確認されたとされています。

人の名前も挙げられています。arXivの著者はPSIのDavid Turtureanの1人です。PSIによれば、Turtureanはシステムを開発し、問題の範囲を定め、システムをその問題で実行し、モデルに最初の草稿を書かせました。論文には「この論文の数学的な主張はAIモデルによって生成された」とあります。PSIのアドバイザーであるJim Halversonは「証明を監査し」、同じくアドバイザーのPhiala Shanahanは「Leanの形式化についてコメントした」とされています。¹アーロンソンはこの取り組みをTurtureanとHalversonが率いたと記していますが、⁴PSIの説明では、主導はTurtureanで、監査がHalversonです。

PSIの証明は、人間の仕事に大きく依拠しています。PSIによれば、証明は「Shachar LovettとJiapeng Zhangの計画に従っている」ものです。2人は1つの不等式を予想として残しており、証明はそれを新しい不等式に置き換えています。また、David Reimerがvan den Berg-Kesten予想に関する研究で示したButterfly Lemmaや、AgarwalとBen-David、KulkarniとTal、Filmus、Hatami、Keller、Lifshitzの結果も使っています。付録Aによれば、モデルのインスタンスは、論文の主要な命題がどれも提案される前に、Reimerの研究とKahn、Saks、Smythの双対不等式を文献から持ち込みました。²

スタンフォードのグループはどう関わっているのか？ この点を曖昧にした報道もありました。2026年8月、Guy Blanc、Jordan Docter、Carmen Strassle、Li-Yang Tanは、特別な場合、すなわち限られた回数の並列ラウンドで動く量子アルゴリズムについて、予想の予測に決着をつける論文を投稿しました。⁸予想全体を解いたとは主張していません。PSIから証明を共有された後、4人は11月7日付の解説を書き、その注記には、証明は「その後著者らに共有され、著者らはそれを理解してこの解説を準備する作業を行った」とあります。⁹この過程でAnthropicの公開モデルを使ったこと、著者らが「AnthropicからもPSIからも金銭的な報酬を受け取っていない」ことも記されています。アーロンソンは、新しい証明は「深さの小さい量子アルゴリズムについての、この夏のAAの証明を特に使ってはいない」と述べています。⁴

専門家はこれまでどう反応しているのか#

私たちが見つけた公開の反応は、短く、日も浅いものです。

最も詳しいのは、11月8日のアーロンソンの投稿です。「証明はまだ理解していない。理解したいとは思っているが」と彼は書いています。「ただ、さしあたり、2つの理由から証明は正しいと考えている。第一にLeanの証明書があり、第二に、人間の専門家（私はもう自分の予想の専門家ではない！）がすでに目を通して理解している」。⁴この問題について慎重になる理由が彼にはあります。2019年、彼はNathan KellerとOhad Kleinが主張した証明についてブログに書きましたが、2人は数週間後に「残念ながら、私たちの証明には重大な欠陥がある」と書いて、それを撤回しました。⁷現在の心境は複雑で、満足、疲労、そして「ロボットより先に人間がこの予想を手に入れられなかったことへの落胆」だといいます。

投稿のコメント欄では、博士課程の多くをこの予想に費やしたと書いたSreejata Kishor Bhattacharyaが、Lovett-Zhangの方法は知っていたがReimerの補題は知らなかったと述べ、AIは文献全体を知っていることで有利になっているのではないかと推測しました。アーロンソンは、Reimerの補題とAgarwal-Ben-Davidを知っている人なら「完成させられたかもしれない」と答えています。

Blancと共著者らは、PSIが公開した声明の中で、PSIに「これは非常に大きな結果だ」と伝えています。¹証明を4つの主要なステップで、より弱い指数で組み立て直した彼らの解説は、私たちが見つけた外部の読解の中で最も本格的なものです。Montanaroの表現は、この予想は「どうやら証明された」というものでした。¹⁶

11月9日の時点で、アンドリス・アンバイニスの公開のコメントは見つかっておらず、モデルや実行についてのAnthropicの声明も見つかっていません。

Leanによる確認で何が言えるのか#

Leanは、証明のすべてのステップを、カーネルと呼ばれる小さなプログラムが検査する言語です。リポジトリ³は、自らの確認について詳しく記録しています。私たちはコードと記録を読みましたが、再ビルドはしていません。

ネガティブテストには注目する価値があります。監査ノートは「公理のレポートの信頼性は、それが読むコンパイル済みファイルの信頼性を超えない」と述べており、¹²プロジェクトは、通常のビルドが受理する偽の証明を作って、その理由を示しています。別のチェッカーによる再実行（replay）を行うのは、このためです。

確認の外に残るものが4つあります。

形式的な命題が、その予想そのものであるか。 カーネルは、与えられた命題がどんなものであっても、その証明を確認できます。READMEは、この一致は「読者が確認すべきものだ」と述べています。³命題は短く、Mathlibの定義だけを使っているので、¹⁵ここで比較してみます。

項目ごとに見ると、両者は対応しています。違いは2つで、どちらもファイルに説明があります。「次数d」は「d以下」と読まれ、O(1) は数7になっています。これは2つの短い文章についての私たちの読みであり、専門家が同じことをする代わりにはなりません。11月8日、外部の貢献者が、予想をLeanで独立に書き直し、PSIの定理から導くプルリクエストを作成しました。作成者はこれを「明示された解釈のもとでの、命題の一方向の含意」と呼んでいます。私たちが確認した時点では、マージされていませんでした。

量子計算とのつながり。 Leanが検査するのは多項式についての命題です。量子アルゴリズムへの橋渡しは、2009年の論文と新しい論文の1.3節によるもので、リポジトリはこの節をLeanに対応するもののない部分の1つに挙げています。¹⁴アーロンソンはこの議論を数文でまとめていますが、機械はそれを検査していません。

論文。 READMEによれば、論文は「人間の読者のために書かれており、それ自体は機械で検査されていない」ものです。人間は、カーネルが一度も読んでいない文章をたどることができますし、文章は、それが説明する証明と食い違うこともあります。論文とLeanの対応表は、監査の言葉によれば、「どの機械も検査していない」案内です。

基盤と記録。 READMEは、信頼するものとして「Leanのカーネルとコンパイラ、Mathlibの定義、そして確認を実行したマシン」を挙げています。記録されている実行はPSI自身のもので、10月22日と11月6日のものです。「一致するハッシュは確認された入力を特定する。出力はチェッカーが報告した内容を記録する」。¹³リポジトリのコマンドを使えば、誰でも再実行できます。

証明の作られ方について、読者には何が分かるのか#

形式的な証明は、どこから来たかを知らなくても評価できます。功績、コスト、手法がどこまで通用するかは別の問題で、それらについては出どころが重要です。

PSIの開示は、部分的には具体的です。とりわけ、命題が提案され証明された順序を示す付録Aの表がそうです。それでも読者には、方向づけのどれだけが問題の範囲を定めた人から、どれだけがモデルを取り巻くシステムから、どれだけがモデル自身から来たのかは分かりません。モデルは一般に公開されていないので、外部の人がもう一度実行することはできません。

8月に出た、この予想に関するほかの2本の論文は、より詳しい記述がどのようなものになりうるかを示しています。Blancらは「ChatGPT 5.4を、文献検索、手書きのノートの電子化、証明の確認、原稿整理に使用した」と書いています。⁸関連する並列クエリの結果を証明したQipeng LiuとSaachi Mutrejaは、役に立ったプロンプトの与え方を説明したうえで、「この方向づけのない、より自由な試みはうまくいかなかった」と付け加えています。¹⁰この一文は、結果がどのように得られたかについて、ほかの研究者に何かを伝えています。こうした失敗がなぜ見えなくなりやすいのかは、AI研究エージェントは否定的な結果を隠すのかで取り上げました。

誰が何に責任を負うのか#

文書はこの点について明確で、この区分は念頭に置いておく価値があります。

• 論文の正しさ：David Turturean。開示によれば、「草稿を自ら確認して編集し、その正しさに責任を負う」。²
• 監査：PSIの説明によればJim Halverson。どちらの文書にも、監査の範囲は書かれていません。
• 形式的な命題の忠実さ：それを読む人。リポジトリがそう述べています。
• Anthropicのモデルが使われたという主張：PSI。
• モデル：何についても責任を負いません。モデルの名前は開示に挙げられますが、主張されたことの何についても、モデルは責任を負いません。

この話でのPapexの役割は小さなものです。アーロンソン＝アンバイニス予想のページ（英語）は、/ai-claims（英語）のすべての項目と同じように、PSIの発表を1件のAI支援の主張として、主張者自身の言葉と、出典の記述どおりのモデル名とともに載せています。そこに表示される状態はOPENです。Papexは状態を名前の挙がった出典（ここでは2014年の論文）から取り、証明を判定しないからです。掲載は主張への案内です。その主張が正しいかどうかについては何も述べていません。

この話に欠けているのは、作成の記録です。研究のどの版がいつ固定されたのか、誰がそれに責任を持ったのか、各人と各ツールが何をしたとされているのか、という記録です。この証明について署名されたPapexの記録は存在しないので、ここまでの内容はすべてPSIの文書に基づいています。また、そのような記録は、どのシステムのものであっても、数学が正しいことを示すものではありません。その仕事をしているのは、Leanと、証明を読んでいる人々です。

全体像をさらに明らかにするものは、次のとおりです。専門家による文書での確認や専門家が見つけた誤り、査読、形式的な命題の独立した確認、アンバイニスのコメント、そしてPSIまたはAnthropicからのモデル名とバージョンです。

利害関係について：PSIが使用したと報告しているモデルはAnthropicのものであり、この記事はAnthropicのモデルであるClaudeを使って下書きされました。読者は、この点を念頭に置いて本記事を評価し、下記の出典を確認してください。

出典#

1. A proof of the Aaronson-Ambainis conjecture（PSI、2026年11月6日）、2026年11月9日確認 ↩ a b c d e f
2. A proof of the Aaronson-Ambainis conjecture（David Turturean、arXiv:2611.09773、2026年11月6日）、全60ページ、2026年11月9日確認 ↩ a b c d e f g h i
3. physical-superintelligence/aaronson-ambainis（GitHub）、README、コミット 2a6ceae、2026年11月9日確認 ↩ a b c
4. Aaronson-Ambainis Conjecture proved! (By AI, of course) とコメント（Scott Aaronson、Shtetl-Optimized、2026年11月8日）、2026年11月9日確認 ↩ a b c d e f g h
5. The Need for Structure in Quantum Speedups（Scott Aaronson、Andris Ambainis、arXiv:0911.0996、バージョン3、Theory of Computing 10、2014年）、2026年11月9日確認 ↩ a b c
6. The Aaronson-Ambainis Conjecture (2008-2019)（Scott Aaronson、Shtetl-Optimized）、2026年11月9日確認 ↩
7. Quantum speedups need structure（Nathan Keller、Ohad Klein、arXiv:1911.03748、2019年12月2日に撤回）、2026年11月9日確認 ↩
8. Quantum Speedups Require Structure or Depth（Guy Blanc、Jordan Docter、Carmen Strassle、Li-Yang Tan、arXiv:2608.19158、2026年8月19日）、2026年11月9日確認 ↩ a b
9. Proof of the Aaronson–Ambainis Conjecture: An Exposition（Guy Blanc、Jordan Docter、Carmen Strassle、Li-Yang Tan、2026年11月7日）、2026年11月9日確認 ↩
10. Parallel Quantum Advantage with Limited Adaptivity Requires Structure（Qipeng Liu、Saachi Mutreja、arXiv:2608.20297、2026年8月20日）、2026年11月9日確認 ↩
11. Verifiable Quantum Advantage without Structure（Takashi Yamakawa、Mark Zhandry、arXiv:2204.02063）、2026年11月9日確認 ↩
12. リポジトリのノート、Axiom audit、2026年11月9日確認 ↩
13. リポジトリのノート、Verification、2026年11月9日確認 ↩
14. リポジトリのノート、Paper to Lean、2026年11月9日確認 ↩
15. リポジトリのファイル、Conjecture.lean、2026年11月9日確認 ↩
16. XでのAshley Montanaroの投稿（2026年11月7日）、投稿の公開ミラーで閲覧、2026年11月9日確認 ↩ a b
17. XでのPedro Domingosの投稿（2026年11月7日）、投稿の公開ミラーで閲覧、2026年11月9日確認 ↩