【ITニュース解説】Aaronson-Ambainis conjecture proved: an unreleased Anthropic model settles the 18-year-old quantum question, Lean-checked

「Aaronson-Ambainis予想」という、量子コンピュータに関する長年の未解決問題が、AIによって証明された。この予想は18年前から専門家の間で議論されてきた課題であり、その証明はさらに「Lean」と呼ばれる特別なソフトウェアによって厳密に検証された。

Aaronson-Ambainis予想とは、量子コンピュータが従来のコンピュータに比べてどれくらい速くなるか、という根本的な疑問に関するものだ。量子コンピュータは、特定の種類の計算において「指数関数的な加速」と呼ばれる劇的な速度向上をもたらすと期待されている。これは、従来のコンピュータでは計算に何億年もかかるような問題を、量子コンピュータなら数分で解けるようになるかもしれない、という意味合いを持つ。しかし、このような劇的な加速は、入力データに「特定の構造」や「隠れたパターン」がある場合にのみ可能だと考えられてきた。例えば、大規模な数の素因数分解など、入力に特定の性質が隠れている問題では、量子コンピュータがその構造を巧みに利用して高速化を実現できる。

しかし、もし入力データが何のパターンも持たない「ランダムな入力」だった場合、それでも量子コンピュータは指数関数的に速くなるのか、という疑問があった。AaronsonとAmbainisは、もしある数学的な性質（多項式に関する予想）が正しければ、量子コンピュータはランダムな入力に対して指数関数的な速さではなく、せいぜい「多項式的な速さ」しか実現できないことを示した。多項式的な速さとは、例えば計算時間が入力のサイズNに対してNの2乗やNの3乗といった形で増加する速さで、指数関数的な速さほどではないが、それでも従来のコンピュータよりは速くなる可能性がある。この予想の証明は、量子コンピュータが持つ計算能力の「限界」を明らかにする上で非常に重要な意味を持っていた。

この長年の未解決問題を解決したのは、Physical Superintelligence (PSI) というAIを専門とする研究所が開発した研究システムだった。このシステムは、Anthropic社が開発した、まだ一般には公開されていない最先端のAIモデルを使用していた。これは、我々が通常利用できるAIよりもはるかに高度な能力を持つAIが、人間には18年間も解けなかった困難な数学の問題を解決したということを意味する。 AIが証明を見つけ出した後、その結果はさらに二度改善され、最終的に「Lean」という特別なソフトウェアに受け入れられた。Leanは「定理証明支援系」と呼ばれるツールで、数学的な証明の全てのステップをコンピュータが論理的に厳密にチェックすることを可能にする。人間による証明では、見落としがちな論理の飛躍や単純な計算ミスが含まれることがあり得るが、Leanのようなシステムを使えば、その証明が完全に論理的に正しいかをコンピュータの力で保証できる。これは、数学の証明の信頼性を極めて高いレベルに引き上げる画期的な方法であり、今回の証明の正当性を強力に裏付けるものだ。

この証明が具体的に示したのは、もしある多項式が特定の変化量を持つ場合、その多項式の出力は、いくつかの入力ビット（情報の最小単位）の影響を強く受ける、という数学的な境界だ。これをより平易に言えば、量子コンピュータが「はい」か「いいえ」の答えを出す確率を、従来のコンピュータがある程度の誤差範囲内で予測できるようになることを意味する。そして、その予測に必要な入力データの読み取り回数は、量子コンピュータが読み取る回数の「固定の乗数」でしか増えない、つまり指数関数的には増えないという結論が導かれた。 この結果は、「ランダムな入力」に対しては、量子コンピュータは指数関数的な計算時間の節約はできない、という決定的な限界を示している。つまり、指数関数的な加速は、あくまで入力データに「珍しいパターン」すなわち「構造」が含まれている場合にのみ可能である、という境界線が明確に引かれたことになる。

今回の成果は二つの大きな点で重要である。 一つは、量子コンピューティングの分野において、長年の未解決問題が解決され、量子コンピュータが劇的な速度向上を実現するには、入力データの「構造」がいかに重要であるかが改めて示されたことだ。構造を持たないランダムな問題に対しては、過度な期待は持てないという現実的な見方を提供し、今後の量子アルゴリズムの研究や応用開発の方向性を示す貴重な指針となるだろう。 もう一つは、AIの能力の進化を示す非常に重要な事例であることだ。人間が18年間も解決できなかった高度な数学問題をAIが解決し、さらにその証明が機械によって検証されたという事実は、AIが科学研究の最前線において強力なツールとなる可能性を強く示している。また、今回使用されたAIモデルが一般公開されていないものであるという点も注目に値する。これは、公開されているAIモデルの能力と、企業内部で開発されている最先端モデルの能力との間に、大きな隔たりがあることを示唆しており、AIの進化のペースがこれまで考えられていた以上に速い可能性も指摘されている。

ただし、この証明にはいくつかの注意点がある。最も重要なのは、この証明はまだ「査読（ピアレビュー）」を経ていないという点だ。査読とは、その分野の専門家が論文の内容を詳細にチェックし、論理的な誤りや結論の妥当性を評価する科学的なプロセスであり、科学的な発見が正式に認められるためには不可欠な手順である。 また、Leanというソフトウェアが証明を検証したことは確かだが、Leanが検証した「形式的な記述」が、元のAaronson-Ambainis予想の「人間が理解できる記述」と完全に一致しているかを、専門家が確認する必要がある。つまり、AIが正しい証明を生成し、機械がそれを正しく検証したとしても、その機械の言葉が人間の意図した問題と本当に合致しているのか、という最終確認は人間の専門家の手に委ねられているということだ。 さらに、この結果は、量子コンピュータが特定の「構造化された問題」（例えば、ショアのアルゴリズムが扱う素因数分解など）で依然として指数関数的な加速を見せる可能性を否定するものではないことも理解しておくべきだ。あくまで「ランダムな入力」に対する限界を示している。

今回のAaronson-Ambainis予想の証明は、量子コンピューティングの理論的な境界を明確にすると同時に、AIの進化が科学のフロンティアをどのように押し広げているかを示す象徴的な出来事である。機械が高度な数学的発見を生み出し、その正確さを機械自身が検証するという、新たな研究のサイクルが現実のものとなりつつある。これからの技術革新の動向を理解する上で、今回の成果は重要な一歩として記憶されるだろう。専門家による最終的な検証が待たれるが、この成果は間違いなく科学史に名を刻む可能性を秘めている。