A 0.651-approximation to quantum Max Cut via Rydberg atoms

技術要約：リドベリ原子による量子最大カットへの0.651近似

問題の定義
本論文は、反強磁性ハイゼンベルク・ハミルトニアンの基底状態エネルギーを見つけることと同等である、量子最大カット（QMC）問題を取り扱う。この問題はQMA完全であり、ユニバーサル量子コンピュータを用いても効率的に解くことができないことを意味する。目的は、最適な基底状態エネルギーに対して特定の比率（$\alpha$）の範囲内で解を保証する近似アルゴлоリズムを見つけることである。半正定値プログラミング（SDP）緩和のみに依存する現在の最先端の古典的手法は、$\alpha = 0.614$ の近似比を達成している。

手法：ハイブリッド量子・古典アプローチ
著者らは、リドベリ原子系の自然な量子ダイナミクスと、古典的な最適化手法（SDPおよびランダム化丸め）を統合したハイブリッドアルゴリズムを提案している。この手法は、以下の4つの段階を経て進行する：

1. エンコーディングとアニーリング:
   グラフ $G=(V, E, \omega)$ によって定義されるQMCインスタンスが、リドベリ原子アレイへとエンコードされる。リドベリ・ハミルトニアン $H_r$ の静的な部分は、グラフのエッジに対応する $XX + YY$ 相互作用項を含むように構成される：
   $$H_r = \sum_{(ij) \in E} \omega_{ij} (X_i X_j + Y_i Y_j)$$
   システムは、近似基底状態 $\varrho_r$ を準備するためのアニーリング手順を経る。

2. 測定と制約の定式化:
   アニーリングされた状態 $\varrho_r$ において、すべてのエッジに対する期待値 $\langle X_i X_j + Y_i Y_j \rangle$ が測定される。これらの値は、後続の古典的最適化ステップのための経験的な制約として機能する。

3. 半正定値プログラミングと丸め:
   擬似モーメント行列 $\Delta$ が、リドベリの測定から得られた制約およびパウリ演算子の代数関係に従って、SDPを通じて最適化される。この行列は、ランダム投影技術（コレスキー分解に続く $\mathbb{R}^{4n}$ から $\mathbb{R}^3$ へのランダム投影）を用いて、積状態 $\varrho_p$ へと丸められる。

4. 最終状態の選択:
   アルゴリズムは、より低いエネルギーを持つ状態、すなわちリドベリ基底状態 $\varrho_r$ または古典的に丸められた積状態 $\varrho_p$ のいずれかを返す。

主要な理論的貢献
本論文は、0.651 という条件付き近似比を確立し、既知の最良の比率である0.614を上回っている。その導出は、主に2つの理論的洞察に基づいている：

• リドベリ基底状態による下界: 著者らは、完全なQMCハミルトニアン（$H_{qmc}$）の基底状態エネルギーが、リドベリ・ハミルトニアン（$H_r$）のエネルギーによって下限付けられることを証明している。ハイゼンベルク・モデルの $SU(2)$不変性を利用することで、最適な基底状態において$XX, YY, ZZ$の期待値が等しいことを示している。これにより、リドベリ系から得られた部分的な$XX+YY$ の測定値から、完全なQMCエネルギーを再構成することが可能となる。
• 丸めによる上界: 本論文は、SDPの丸めによって生成された積状態 $\varrho_p$ のエネルギーを分析している。著者らは、測定された相関に基づく、この状態の期待エネルギーの解析的な表現を導出している。
• 比率の最適化: 相関パラメータ $t_{ij}$ に関する最小化問題を解くことにより、これら（リドベリ状態から導かれる下界と、リドベリ状態および積状態の両方からの上界）を組み合わせることで、この0.651という比率が得られる。

結果とロバスト性

• 近似比: アルゴリズムは、$\kappa = 0.651$ の条件付き近似比を達成する。
• ノイズへの耐性: アルゴリズムの重要な知見は、不完全な基底状態準備に対する耐性である。著者らは、リドベリ・アニーリング手順が真のリドベリ基底状態エネルギーのわずか 89% ($\eta = 0.89$) のエネルギーしか生成しない場合でも、0.651の優位性が維持されることを示している。この閾値を下回ると、純粋な古典的SDP手法に対する優位性が減少する。
• 計算複雑性: このハイブリッドアプローチは、古典的な最適化問題の次元を削減する。絡み合い（エンタングルメント）状態を対象とする古典的なスキームは $O(n^4)$ の実変数を必要とするが、このハイブリッド手法は、量子系を利用してエンタングルメント構造の複雑さを処理することで、$O(n^2)$ の変数で動作する。

意義
本論文は、ハイブリッド量子・古典アルゴリズムの新たな経路を切り開いたと主張している。量子ハードウェア（特にリドベリ原子アレイ）と古典的な最適化を組み合わせることで、量子ハードウェアが基礎となるハミルトニアン問題を完全に解けない場合であっても、純粋な古典的手法よりも強力な近似保証が得られることを示している。この研究は、量子プラットフォームが、高品質な下界および古典的丸め手順の開始点を提供する効果的な「プロキシ（代理）」として機能し、純粋な古典的アプローチの計算スケーリングの制限を効果的に回避できる可能性を示唆している。