Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

技術要約：近対称最適化問題における浅いQAOAのフォールトトレラントなコスト

問題提起
MontanaroとZhou [1] は、深度1の量子近似最適化アルゴリズム（QAOA）回路が、特定の近対称制約充足問題（CSP）において、定数確率 $\Omega(1)$ で植えられた解（planted solution）を見つけられることを示した。これに対し、これらの問題を明示的に実現する場合、強力な古典ソルバーに対して指数関数的な実行時間のスケーリングが見られる。これは経験的な指数関数的加速を示唆しているが、初期のフォールトトレラント量子コンピュータ上でこれらの回路を実装するためのリソース要件は不明である。これらの問題のコスト・ハミルトニアンは $\Theta(n^\ell)$ 個の節（clause）を含んでおり（ここで $\ell \ge 5$）、標準的なClifford+T合成を用いてコンパイルすると、非クリフォード・ゲート数は $\tilde{O}(n^\ell)$ のスケーリングを意味する。このスケーリングにより、関連する問題サイズは近未来のフォールトトレラント・ハードウェアの到達範囲を超えてしまう。

手法
著者らは、これらの近対称インスタンスに適用される深度1のQAOA回路のフォールトトレラントなリソースコストを分析しており、特に位相分離層（phase-separator layer）の合成に焦点を当てている。分析は以下の3つの主要なステップで行われる：

1. 位相整合と角度のスケーリング： 著者らは、定数成功確率に必要な位相整合条件を再検討している。変数置換に関して植えられた解に対して対称なコスト関数の場合、支配的なハミング・シェルの建設的な干渉を確実にするために、位相分離角 $\gamma$ は $\gamma = \Theta(n^{1-\ell})$ とスケールしなければならない。
2. 小角合成： $\gamma$ がシステムサイズとともに減少するという事実を利用して、著者らは小角Clifford+T回転合成技術（具体的にはBotheら[9]によるもの）を適用している。彼らは、小角回転が高確率で恒等写像によって近似され、少数の回転のみが非クリフォード合成を必要とする、準確率および確率混合の定式化を利用している。
3. 明示的な節のコンパイルとリーク解析： 著者らは、値オラクルモデル（コスト $C(x)$ のみを参照するモデル）から、回路コンパイルに必要な明示的な節リストモデルへと移行している。彼らは、明示的な節リストから導出されたコスト関数のフーリエ係数を分析し、コンパイルプロセスが意図せず解を露呈させていないかを判断している。
4. 欺瞞的なインスタンスの構築： 明示的な構造を利用する古典的攻撃に対する堅牢性をテストするために、著者らは「植えられていない（unplanted）」近対称インスタンスを構築している。これらのインスタンスは、指数関数的に大きな最適ハミング・シェルを含むNP困難な部分問題を特徴とし、局所探索アルゴリズムをトラップするように設計されたコスト景観を持つ。

主な貢献と結果

• 二次的な非クリフォード・スケーリング： 主要な結果は、これらのインスタンスにおける深度1のQAOAの非クリフォード・コストが、節の局所性 $\ell$ や希薄化率に依存せず、$\tilde{O}(n^2)$ に減少することである。この減少は、総位相質量（$m\gamma$、ここで $m$ は節の数）が $n$ に対して線形にスケールし、小角合成のコストがこの位相質量の平方に依存するためである。その結果、以前は $\tilde{O}(n^\ell)$ のスケーリングにより実現不可能と考えられていた問題サイズが、初期のフォールトトレラント・デバイスで実行可能になる（図2参照）。
• 植えられた家族における古典的リーク： 文献[1]で研究された植えられた家族について、著者らは、コンパイルに必要な明示的な節リストが植えられた解を露呈させることを示している。位相整合条件（$F'(1/2) \neq 0$）は、コスト関数の次数1のフーリエ係数（局所場）の符号を固定する。これらの符号は、節リストの単純な線形時間スキャンを通じて、植えられた解 $s$ を直接的に明らかにする。したがって、QAOAは定数確率で成功する一方で、明示的な実装は問題を古典的に自明なものにする。
• 植えられていない困難なインスタンスの存在： 著者らは、小角レジームと $\tilde{O}(n^2)$ のコストスケーリングが、植えられた解の存在に依存しないことを示している。彼らは、植えられた解を持たない近対称インスタンスを構築しており、そこでは以下のことが成立する：
  • グローバルな最適解が指数関数的に大きなハミング・シェル内にある。
  • そのシェル内で正確な最適解を見つけることはNP困難である。
  • コスト景観は「欺瞞的」であり、高いエネルギー障壁によって隔てられた劣なセクターに局所探索や汎用MaxSATソルバーをトラップする。
  • 小角における深度1のQAOAは、同じ $\tilde{O}(n^2)$ の非クリフォード・コストで出力を最適シェルに集中させる。
  • これらの植えられていないケースでは、次数1の係数は一様であり、解を明らかにしないため、特定の対称構造を利用しない古典的アルゴリズムに対する困難性が維持される。

意義
本論文は、近対称問題における低深度QAOAの経験的な加速が、以前想定されていた $\tilde{O}(n^\ell)$ ではなく、大幅に低いリソース、具体的には $\tilde{O}(n^2)$ の非クリフォード・ゲートを用いて実現可能であることを確立している。これにより、これらの浅い小角回路が、初期のフォールトトレラント・ハードウェアにとって現実的なターゲットとなる。

しかし、著者らは重要なトレードオフがあることを控えめに指摘している。小角合成を可能にするメカニズム（コヒーレントな局所場）は、同時に植えられたシナリオにおいて解を古典的攻撃に対して露呈させてしまう。本研究の意義は、浅いQAOAが最適化のためのリソース効率の高い経路を提供するレジームを特定すると同時に、その効率を可能にする特定の構造的特性が諸刃の剣となり得ることを明らかにしている点にある。著者らは、中心となる未解決の問いは、この「安価な」小角レジームを、解が低次の古典的攻撃から隠されたままの状態を維持できる、より深い回路や異なる問題構造へと拡張できるか、すなわち、フォールトトレラントとして安価でありながら、かつ古典的に耐性のある真の量子優位性を達成できるかであると結論付けている。