Evaluating QAOA expectation values can be as hard as counting optimal solutions

コンピュータが単に数値を計算するだけでなく、確率と踊る世界を想像してみてください。これは量子コンピューティングという領域であり、今日のスーパーコンピュータでは宇宙の年齢よりも長い時間を要するほど、複雑に絡み合った問題を解決することを約束する分野です。このダンスの中心にあるのは、「量子近似最適化アルゴリズム（QAOA）」と呼ばれる人気のルーチンです。QAOAをハイテクな宝探しだと考えてください。あなたには多くの経路（問題）がある地図があり、最も多くの金塊（最良の解）へと続く一つの経路を見つけ出したいと考えています。量子コンピュータは特別な「重ね合わせ」状態、つまりすべての可能な経路が同時に混ざり合った魔法のような状態を準備し、それから「レイヤー」や「深さ」と呼ばれる一連のステップを通じて、最後にあなたが実際に見たときに、最良の経路が最も輝いて見えるように、確率の傾きを調整しようと試みます。

宝探しがうまくいっているかどうかを知るために、科学者たちは「期待値」を確認する必要があります。平易な言葉で言えば、これは量子コンピュータのダンスを、すべてのコインを数えるためにダンスを止めることなく、ダンスがどれくらい金塊に近づいているかを確かめるために、素早く覗き見ることのようなものです。長い間、研究者たちは、もしダンスがステップ一つ（深さ $p=1$）だけであれば、このスコアを確認することは簡単なレシピを読むことのように簡単であることを知っていました。しかし、ダンスが二ステップ、あるいはそれ以上のステップへと複雑になったらどうなるでしょうか？ Wangとその同僚たちによる最近の研究は、これらのより深いダンスのスコアを確認することは非常に困難であり、その難しさは元の宝探し自体を解くことと同じくらいであることを示しました。しかし、それは単に「一つの良い経路」を見つけるのと同じくらい難しいのでしょうか、それとももっと難しいのでしょうか？

Stuart Hadfieldによるこの論文は、その問いを深く掘り下げています。著者は、2つ以上のレイヤーを持つQAOAにおいて、スコアを確認することは単に一つの最良の解を見つけることと同じくらい難しいだけでなく、存在する「すべての」最良の解を数えることと同じくらい難しいのだと証明しています。コンピュータサイエンスの世界では、一つの解を見つけることは困難な挑戦ですが、それらすべてを数え上げることは、古典的なコンピュータにとってさらに不可能に近いとされる、全く別次元のモンスター級の難問です。Hadfieldは、アルゴリズムに二番目のレイヤーを加えた瞬間に、この「計数モンスター（counting monster）」が現れることを示しています。この論文は単にそれを示唆するだけでなく、特定のタイプの問題グラフを構築することで、QAOAのスコアを計算しようとするあらゆるコンピュータが、本質的に不可能な計数問題を解かざるを得なくなることを示す厳密な数学的証明を提供しています。これは、これらのより深い量子アルゴリズムにとって、それらがどれほど上手くいっているかをチェックするという行為自体が、最悪の場合、完璧な量子マシンを使ってダンスを実行できたとしても、古典的なコンピュータの手には根本的に届かないタスクであることを意味しています。

宝探しは複雑になる

このマジックトリックを分解してみましょう。QAOAアルゴリズムは「MaxCut（最大カット）」問題を解くように設計されています。パーティーに集まった友人たちのグループを想像してください。あなたは彼らを二つのチーム（チーム・レッドとチーム・ブルー）に分けたいと考えています。目標は、二つのサイドの間で最大限の数の「友情」が断ち切られるようにチームを配置することです。これが「MaxCut」です。いくつかの配置は他の配置よりも優れており、絶対的な最良の配置を見つけることは、友人が増えるほど難しくなる古典的なパズルです。

QAOAアルゴリズムは、量子コインを回転させることで、この最良の配置を見つけようとします。まず全員を重ね合わせ状態（赤でもあり青でもある状態）にし、それから一連の「ひねり（レイヤー）」を加えます。ひねりを追加すればするほど、ダンスはより洗練されたものになります。ダンスが機能しているかどうかを見るために、科学者たちは「期待値」を計算します。これは、量子ダンスの中で平均してどれくらいの数の友情が断ち切られているかを教えてくれる「スコア」のようなものです。

単一のひねり（$p=1$）の場合、このスコアを計算するのは簡単です。ナプキンに書き留めることができます。しかし、二番目のひねり（$p=2$）を加えると、事態は奇妙になります。これまでの研究では、このスコアを計算することは「NP困難」である、つまり単一の最良のチーム配置を見つけることと同じくらい難しいことが示されていました。しかし、Hadfieldの論文はこう言います。「待って、実はそれよりもっと悪い。」

計数モンスター

Hadfieldの主な発見は、難易度に関する理解の劇的なアップグレードです。彼は、$p \ge 2$ の場合のスコア計算が単に「NP困難（一つの解を見つけること）」であるだけでなく、**「#P困難（#P-hard）」**であることを証明しました。

その違いを理解するために、あなたが探偵だと想像してください。

• NP困難とは、「犯行を行った容疑者を一人でも見つけられるか？」と問われるようなものです。難しいですが、運が良かったり一生懸命取り組んだりすれば、一人は見つけられるかもしれません。
• #P困難とは、「合計で何人の容疑者が犯行を行ったのか？」と問われるようなものです。あなたは一人残らず全員を見つけ出し、数え上げなければなりません。

コンピュータサイエンスの世界では、単に一つを見つけることよりも、数を数えることの方が一般的にはるかに難しいと考えられています。Hadfieldは、2つ以上のレイヤーを持つQAOAの場合、スコアを計算するための数学が、完全な解の総数を数え上げることを強いることを示しています。

マジック・ガジェット

彼はどのようにしてこれを証明したのでしょうか？ Hadfieldは、コンピュータを捕まえるための罠のような、巧妙な「ガジェット」を作り上げました。彼は標準的なMaxCut問題を取り、その周囲に巨大で複雑なグラフを構築しました。このグラフには、特別な「アンカー（固定点）」と「変数」ブロックがあります。

トリックはその設計にあります。量子コンピュータがこの特定のグラフ上でダンスを実行すると、最終的なスコップ（期待値）は「ローラン多項式」と呼ばれる巨大な数学的表現になります。この表現は、変数の異なる累乗（例えば $z^1, z^2, z^3...$）を持つ項の長い文字列のようなものです。

Hadfieldは、この文字列における「最高次（extreme coefficient）」が秘密を握っていることを示しました。もし、このスコアを完璧に計算できるなら、この最高次を抽出することができます。そして、ここが肝心なのですが、その特定の数値の大きさは、元の問題に対する完全な解の総数に直接比例しています。

したがって、もしこのグラフに対するQAOAスコアを容易に計算できるなら、あなたは即座に「計数モンスター」問題の答えを知ることになります。数えることは古典的なコンピュータにとって効率的に行うことは不可能であると信じられているため、QAOAスコアを計算することもまた、彼らにとっては不可能であるに違いありません。

「一つのエッジ」の驚き

論文はさらに驚くべき展開を見せます。「よし、全体のスコアを計算するのは難しいかもしれないが、たった一つの特定の友情（単一のエッジ）に関するスコアを計算するのは簡単ではないか？」と思うかもしれません。

Hadfieldは、それは違うと言います。彼は、たとえ量子コンピュータに対して、二人の特定の人々の間の相関関係（「二量子ビット・コレーター」のような $\langle Z_r Z_s \rangle$）だけを教えるよう求めたとしても、問題は依然として #P困難のままであることを証明しました。難しさは全体像にあるだけでなく、アルゴリズムの最小単位の細部にまで刻み込まれているのです。

これが将来に意味すること

この論文は明確な境界線を引いています。

• 深さ $p=1$: 簡単。スコアを効率的に計算できます。
• 深さ $p \ge 2$: 困難。スコアを計算することは、すべての最適な解を数えることと同じくらい困難です。

これには大きな意味があります。多くの現代的なアルゴリズムは、より良いスコアを得るために「ひねり（パラメータ）」を調整しながら、QAOAを使用して機械を訓練します。もしスコアの計算がこれほどまでに難しいのであれば、古典的なコンピュータ上でこれらのアルゴリズムを訓練すること（量子マシンがどのように機能しているかを確認すること）は、深い回路においては不可能かもしれません。

著者も、これが量子コンピュータを無用にするという意味ではないと述べています。実際には、むしろそれらが「より有用」であることを意味しているのかもしれません。もし古典的なコンピュータがスコアをチェックすることさえできないのであれば、おそらく量子コンピュータこそがそれを実行できる唯一の存在だからです。しかし、論文はまた、この「困難さ」はワーストケースのシナリオであることも警告しています。これは、すべてのグラフが解く不可能なわけではないことを意味します。ただ、数学が古典的なコンピュータにとって破綻してしまうような、特定の厄介なグラフが存在するということを意味しているのです。

まとめ

Stuart Hadfieldの論文は、量子コミュニティへの警鐘です。それは、QAOAにレイヤーを追加してより強力にすればするほど、単に問題を解くのが難しくなるだけでなく、「自分たちの仕事が正しいかどうかを確認する」という問題さえも指数関数的に難しくなるということを伝えています。私たちは、量子ダンスを簡単に検証できた世界から、ダンスの検証自体がコンピュータサイエンスにおける最も困難なパズルの一つである「計数問題」を解くことを要求される世界へと移行したのです。量子領域においては、深く進めば進むほど、数学はより神秘的になるということを、この論文は思い出させてくれます。