Quantum-echo Markov process for combinatorial optimization

技術要約：組合せ最適化のための量子エコー・マルコフ過程

問題提起
本論文は、有限のリソースを持つ量子力学（具体的には量子アニーリング（QA）および量子近似最適化アルゴリズム（QAOA））を組合せ最適化に利用する際の課題に取り組んでいる。QAおよびQAOAは有望であるものの、近年の研究では、有限時間または固定深さのレジームにおいて、これらが実質的な局所構造を示すことが指摘されている。具体的には、それらのダイナミクスは基礎となるグラフの有界な近傍に制限されることが多く、その結果、局所解から効果的に脱出できないか、あるいは探索範囲を広げすぎると本質的にランダムなサンプリングとなってしまう。核心となる問題は、反復探索プロセスにおける遷移カーネルを、ハミング空間においては非局所的（遠く離れた構成を探索するため）でありながら、エネルギー空間においては局所的（大きく有害なエネルギー変化を避けるため）であるように設計することであり、これにより、探索をランダム化することなく局所解からの効率的な脱出を可能にすることである。

手法
著者は、そのような遷移カーネルを構築するために、量子エコー・マルコフ過程を提案している。この過程は、ユニタリ演算子 $\hat{U}$（QAまたはQAOAから導出される）と、局所的なエルミート・ユニタリ演算子の集合 $\{\hat{V}_i\}$（単一スピン反転 $\hat{\sigma}^x_i$ として選択される）によって定義される。

1. 量子エコー・ダイナミクス: 遷移は、シーケンス $\hat{U} \hat{V}_i \hat{U}^\dagger$ によって生成される。計算基底状態 $|z\rangle$ から出発し、システムは $\hat{U}^\dagger$ によって前方へ進化し、局所的な摂動 $\hat{V}_i$ を受け、$\hat{U}$ によって後方へ進化する。
2. 遷移行列: 構成 $z$ から $z'$ への遷移確率は、状態 $|\psi_i(z)\rangle = \hat{U} \hat{V}_i \hat{U}^\dagger |z\rangle$ を計算基底で測定することによって決定される。
3. 局所性指標: 遷移を特徴付けるために、著者は2つの指標を定義している。
   • ハミング空間の局所性 ($d_H$): 現在の構成と候補となる構成の間の平均ハミング距離。
   • エネルギー空間の局所性 ($d_E$): 遷移によって誘起される平均二乗エネルギー変化 ($\Delta C^2$)。
4. モデル: このフレームワークは、ランダム・イジング・モデル（エネルギーとハミング構造が相関している）およびランダム・エネルギー・モデル（REM）（両者が無相関である）に対してテストされている。
5. 最適化戦略: 2つの反復最適化アルゴリズムが提案されている。
   • 量子エコー局所最適化: 候補となる構成が $\Delta C \leq 0$ を満たす場合にのみ、それを受理する。
   • 貪欲降下法を用いた量子エコー局所最適化: 量子エコー遷移の後、次のイテレーションに移る前に、局所解に到達するための貪欲な単一スピン反転降下を行う。

主要な貢献とメカニズム

• 構造化された遷移の設計: 本論文は、アニーリング時間 $\tau$ またはQAOAのレイヤー数 $p$ を増やすことが、ハミング空間における非局所性（非局在化）を同時に増大させることを示している。しかし、エネルギー空間における局所性の振る舞いはモデルによって異なる。REMでは、$\tau$ または $p$ が増加するにつれて $d_E$ が減少（局所性が向上）するが、ランダム・イジング・モデルでは、$d_E$ は $p$ や $\tau$ に対してほぼ独立している。驚くべきことに、REMにおいては、これらの遷移は単一スピン反転よりもハミング空間ではより非局所的であるにもかかわらず、エネルギー空間においてはより局所的になり得る。
• ハミング非局在化のメカニズム: これは**演算子の広がり（operator spreading）**に起因する。$\tau$ または $p$ が増加するにつれ、ハイゼンベルク描像における低次のパウリ・ストリングは、多くのスピンを含む高次のストリングへと進化し、これにより遷移がハミング空間における遠く離れた構成同士を接続することが可能になる。
• エネルギー局在化のメカニズム: これは、有効ハミルトニアン $\hat{U}^\dagger \hat{C} \hat{U}$ の固有状態のコスト関数 ($C_z$) とハミング重み ($w_z$) の間に動的に生成される相関に起因する。
  • QAにおいては、指数関数的に小さいエネルギー間隔が分解される前の、粗視化された準断熱的ダイナミクスからこの相関が生じる。
  • QAOAにおいては、回路パラメータの変分最適化によって生成され、これにより有効ハミルトニアンにおける低次項が強化され、$C_z$ と $w_z$ の間に線形な相関が生まれる。
• 貪欲降下の役割: 本研究では、量子ダイナミクスが必要な探索（非局所性）を提供する一方で、過度なエネルギー空間の局在化は、必要な遷移を抑制することで性能を低下させ得ることが示された。貪欲降下ステップ（搾取）を組み込むことは性能を大幅に向上させ、量子ダイナミクスによる探索と古典的な貪欲ステップによる搾取の相補的な役割を浮き彫りにしている。

結果

• 局所性のチューニング: ランダム・イジング・モデルおよびREMに関する数値シミュレーションにより、$d_H$ は $\tau$ または $p$ の増加とともに増加することが示された。REMにおいては、$\tau$ または $p$ の増加に伴い $d_E$ が減少する。また、ランダム位相近似が厳密な結果をよく再現している。ランダム・イジング・モデルでは、$d_E$ は $\tau$ や $p$ に対してほぼ独立しており、厳密な結果とランダム位相近似との間に、小さな $\tau$ および $p$ において乖離が見られる。
• 強磁性鎖: 強磁性イジング鎖において、目標とする最適性ギャップに達するために必要なイテレーション数は、システムサイズ $N$ に対して線形にスケールする。量子エコー・プロセスは、小さな最適性ギャップにおいてランダムな単一スピン反転を凌駕する。ダイナミカル・ドリフトは、熱的ドリフトと「局所欠陥比」の積に近似できることが示されており、この比は回路の深さが増すにつれて1に近づく。
• ランダム・イジング・モデル:
  • 貪欲降下なしの場合: 成功確率 ($p_{suc}$) は $\tau$ または $p$ の増加とともに最初は上昇するが、$\tau$ が大きくなると（QAにおいて）遷移行列がブロック対角（断熱限界）になり、システムがトラップされるため、減少する場合がある。これは、過度なエネルギー空間の局在化が有害となり得ることを示している。
  • 貪欲降下ありの場合: 成功確率は、より小さな $\tau$ または $p$ でも急速に1に近づく。決定的なことに、QAにおいては、非貪欲版が失敗する大きな $\tau$ においても、成功確率は1を維持する。ヒットタイムは $p$ または $\tau$ の増加とともに減少する。
• スケーラビリティ: エネルギー空間の局所性の指標である $\xi$ は、ランダム・イジング・モデルにおいてシステムサイズに対してほぼ独立しており、このメカニズムがより大きなシステムでも持続することを示唆している。

意義と主張
本論文は、量子エコー・マルコフ過程を、調整可能な局所性を備えた構造化された遷移カーネルを設計するためのフレームワークとして確立している。著者らは、有限時間の量子多体系のダイナミクスが、スタンドアロンの最適化器としてではなく、ハイブリッドな量子・古典ループ内でプロポーザル（提案）を生成するために使用されるならば、計算プリミティブとして機能し得ると主張している。

著者は、ランダム・イジング・モデルの結果はスケーラビリティを示唆しているものの、REMにおける漸近的なスケーラビリティや、大規模なシステムにおけるQAOAパラメータの学習可能性（潜在的なバレン・プラトーの問題）については未解決の課題であると謙虚に述べている。また、より困難な問題に対する最適なアニーリング時間や深さ、および、より洗練された受理ルール（例：アップヒル移動の許容）の影響についても、さらなる調査が必要であるとしている。本研究は、有限時間の量子ダイナミクスを、単に最終的な解を見つけるためだけでなく、構造化された探索を通じて近似的な最適化を系統的に改善するための手段として活用する道筋を提供するものである。