Anthropicの謎のモデルが量子計算の重要な予想を攻略、数学界を20年近く悩ませてきた難問が解決

動察 Beating AI速報、AI研究企業Physical Superintelligence（PSI）は、Anthropicの未公開モデルを用いて、数学界を約20年間悩ませてきたAaronson–Ambainis予想を証明したと発表した。AIは稼働3日目にして完全な証明を発見し、Lean数学検証ツールのチェックを通過した。

この予想は2008年に2人の科学者によって提唱され、量子コンピュータの速度優位性がどれほど大きいかを研究するものだ。

量子コンピュータは一部の問題を処理する際、通常のコンピュータより数億倍速くなる可能性がある。例えば非常に大きな整数の因数分解では、通常のコンピュータは既知のアルゴリズムを使うと極めて長い時間がかかる可能性があるが、量子コンピュータは計算時間を大幅に短縮できると期待されている。しかしこの巨大な優位性は通常、問題自体に何らかの数学的規則性が存在することに依存している。

今回AIが証明したのは、入力データが完全にランダムで利用可能な特別な規則性がない場合、「はい」か「いいえ」だけを答える問題において、量子コンピュータはデータ読み取り回数で指数的優位性を得られないということだ。

例えば膨大なランダム数字の中からある結果を判定する場合、量子コンピュータは量子重ね合わせを利用して一度のクエリで複数の位置に関与できる。通常のコンピュータは一度に一つの位置しか読み取れないが、量子アルゴリズムの判定規則を知っていれば、結果に最も影響する数字を優先的に検査し、比較的限られたクエリ回数で量子コンピュータの答えを近似的に予測できる。

これまで数学者は特定の特殊なケースではこれが可能であることを知っていたが、この規則が普遍的に成立することを証明できずにいた。PSIは今回完全な証明を完成させ、約20年続いた理論的問題も解決した。

この知らせが伝わると、ワシントン大学のPedro Domingos教授は量子コンピューティング優位性の夢はすでに崩れたとさえ考えた。

予想提唱者の一人であるScott Aaronsonはその後、この理解は誤りだと指摘した。研究が制限するのは特定の問題において量子コンピュータがデータクエリを何回節約できるかだけで、量子コンピュータの実際の演算速度優位性を否定するものではない。大整数因数分解に用いられるShorアルゴリズムや、量子物理・化学シミュレーションは影響を受けない。

Aaronsonは、自分はまだこの証明を完全に読み解けていないが、Leanがチェックを完了し、他の数学者も査読しているため、結果は正しいと信じていると述べた。また冗談めかして、自分の予想がついに証明されたことは嬉しいが、人類が最終的にAIより先にそれを解決できなかったことに多少失望しているとも語った。