Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

技術要約：制約付き最適化のための幾何学に基づいた多項式時間量子近似スキーム

問題設定
制約付き組合せ最適化は、ハード制約（例：割り当て、マッチング、ルーティング）に従って最適な構成を見つけることを目的とする。特定の扱いやすい部分集合に対しては古典的なアルゴリズムが存在するが、多くの問題はNP困難である。量子アプローチ、特に量子近似最適化アルゴリズム（QAOA）は、近年のデバイスにおいて以下の課題に直面している：

1. 実現可能性（Feasibility）： 標準的なQAOAは、ハード制約によって定義される実現可能な部分空間の外側をサンプリングしてしまうことが多い。
2. ノイズ： デバイスノイズが制約違反を引き起こし、サンプルの品質を低下させる。
3. 保証： 既存の手法は、現実的なノイズ条件下において、厳密なエンドツーエンドの性能保証（高い確率で最適解を見つけるための多項式時間の実行時間）を欠いていることが多い。

本論文は、次の問いに取り組んでいる：ノイズを含む量子サンプラーは、いつ、性能保証を持つエンドツーエンドの多項式時間アルゴリズムを可能にするのか？

手法
著者らは、量子サンプリングと決定論的な古典的後処理を統合した完全なパイプラインである、Noisy Polytime Hybrid Quantum-Classical (NP-HQ) アルゴリズムを提案している。この手法は、以下の3つの柱に基づいている：

1. OFMカーネルとCE-QAOA：
   本アプローチは、巡回セールスマン問題（TSP）や二次割当問題（QAP）などの問題を定義するための特定のエンコーディングであるOnah–Firt–Michielsen (OFM) カーネルを利用する。

   • エンコーディング： 各論理ブロックに正確に1つの励起が含まれるワンホット・エンコーディングを使用する。
   • ダイナミクス： ワンホット部分空間を保持するブロック局所的なXYミキサーを用いたConstraint-Enhanced QAOA (CE-QAOA) を採用する。
   • 保証： 先行研究 [1] に基づき、特定の幾何学的条件（位相分離）が満たされる場合、理想的なCE-QAOAサンプラーは、最適解の集合に対して逆多項式的な確率質量（$p_0 = \Omega(n^{-k})$）を割り当てることが示されている。

2. 決定論的な修復とスコアリング：
   ノイズや実行不可能なサンプルを処理するために、パイプラインには古典的な後処理が含まれる：

   • 実現可能性チェック： ワンホット制約を検証する。
   • 修復（Repair）： 決定論的な多項式時間アルゴリズム（具体的には、割当問題に対するハンガリアン法やスワップベースのヒューリスティック）を用いて、ノイズを含む実行不可能なビット列を、最も近い実現可能な解（例：有効な置換）へと射影する。
   • スコアリング： 修復された候補に対して、厳密な目的関数を評価する。
   • 理論的根拠： 修復マップは全変動距離において縮小写像であり、最適解の集合の確率質量を減少させないことが示されている。

3. ノイズ耐性解析：
   著者らは、デバイスノイズと最適サンプリング質量の劣化との関係を示すリプシッツ型の境界を導出している。層あたりの実効誤差が十分に低い場合、ノイズを含む最適質量が逆多項式的に維持される「ノイズ・ウィンドウ」を確立している。これにより、高い確率で最適解を回収するために必要な多項式ショット予算を算出することが可能となる。

主な貢献

1. FPRAS$_q$ (Exact-Hit)：
   理想的なサンプラーが最適解に対して逆多項式的な質量を割り当てる低ノイズ領域において、NP-HQパイプラインは完全多項式時間ランダム近似スキーム (FPRAS$_q$) を構成する。これは、多項式時間（量子回路呼び出し ＋ 古典的後処理）で、確率 $1-\delta$ でグローバル最適解を見つけることを保証する。

2. $\varepsilon$-PTQAS (Approximation)：
   Exact-hit領域を超えて、本パイプラインは$\varepsilon$-多項式時間量子近似スキーム ($\varepsilon$-PTQAS) を提供する。修復による目的関数の膨張が制御されている場合、このアルゴリズムは多項式時間で $(1+\varepsilon)$-近似を実現する。

3. 量子・古典の分離：
   本論文は、NP-HQパイプラインと純粋な古典的戦略との間の条件付き分離を確立している。たとえ古典的サンプラーが以下のものへのアクセスを許容されたとしても：

   • 同等の効率的な修復マップ（ハンガリアン投影）へのアクセス。
   • 制約構造（例：行のワンホット文字列からの一様サンプリング）への完全なアクセス。
   • 多項式時間。
     その古典的サンプラーは、NP $\subseteq$ BPP でない限り、NP困難なカーネル適合ファミリーに対して逆多項式的な最適重なりを再現することはできない。量子的な優位性は、厳密にはサンプリング分布の生成にあり、古典的な処理にはない。

4. Heavy-Hitter QAOA (HH-QAOA)：
   古典的な後処理コストを削減する洗練された手法。量子分布の幾何学を利用することで、アルゴリズムは「ヘビーヒッター」（高頻度サンプル）を特定し、候補セットをフィルタリングする。これにより、近似保証を損なうことなく、古典的な後処理の複雑さを $O(n^{k+4})$ から $O(n^{k+3})$（またはさらなる圧縮によるそれ以下）へと低減させる。

5. ハードウェア実証：
   この完全なパイプラインは、最大100個の論理変数を持つQOptlib TSPインスタンスを用い、2つの異なる127量子ビットIBM Eagle-r3プロセッサ（ibm_brisbane および ibm_sherbrooke）上で実行された。

   • 結果： 強力なノイズ（2量子ビットエラー率 $\sim 10^{-3}$ ～ $10^{-2}$）にもかかわらず、決定論的な修復によりすべてのサンプルにおいて実現可能性が回復された。
   • 性能： 修復された解は、テストされたすべてのケースにおいて、公開されている参照ツアーと同等またはそれを上回る性能を示し、本アプローチの現在のハードウェアにおける実現可能性を証明した。

意義と主張
本論文は、以下の要素を組み合わせた、デバイスノイズ下におけるエンドツーエンドのハイブリッド量子・古典パイプラインに対する最初の最適化保証を提供すると主張している：

• 有限ショットでの最適解回収。
• 決定論的な実現可能性の回復。
• 回復された最適質量に関する明示的な有限ノイズ下限。
• 多項式ショット複雑性と多項式後処理実行時間。

著者らは、制約付き量子最適化は、問題の構造（OFMカーネルによる）と古典的処理（修復マップによる）の両方において、問題の構造が活用される統一されたパイプラインとして捉えられるべきであると論じている。本研究は、NISQ時代においても、浅い制約付き回路と厳密な古典的後処理を組み合わせることで、証明可能な近似スキームおよび競争力のある結果が得られることを示している。

限界と範囲

• 保証は、正の位相分離（$\delta > 0$）と十分なミキサーエンベロープの重みに依存するため、インスタンス依存である。
• 「Exact-hit」の保証は、特定のノイズ・ウィンドウ内でのみ成立する。この範囲外では、スキームは近似スキームへと劣化する。
• 量子・古典の分離は、NP $\not\subseteq$ BPP という仮定に基づいた条件付きである。
• ハードウェア実験では、ハードウェアネイティブな再最適化ではなく、一般的なQAOA最適化からの固定されたウォームスタート・パラメータを使用しており、ノイズのあるデバイスへのパラメータの転移性をテストしている。