Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

技術的要約：半正定値計画問題のための量子交互方向乗算法（QADMM）

問題設定

半正定値計画問題（SDP）は、制御理論、統計学、機械学習、金融、量子情報などの分野に応用される基本的な凸最適化問題である。しかし、大規模なSDPインスタンスを解くことは、古典的なアルゴリズムにとって依然として計算量的に困難な課題である。主なボトルネックは、各反復における線形システムの求解および固有値分解（特に、正定値錐への射影）にかかる高いコストである。QMWU（Quantum Matrix Multiplicative Weights Updates）やQIPM（Quantum Interior Point Methods）といった量子アルゴリズムがこれらの問題を解決するために提案されているが、これらは次元依存性、スパース性パラメータ、または精度要件においてトレードオフに直面することが多い。

手法

著者らは、最も高コストなサブルーチンに対して量子的な高速化を活用しつつ、古典的な一次手法の堅牢性を維持するように設計されたハイブリッド量子・古典アルゴリズムである、**量子交互方向乗算法（QADMM）**を提案している。

1. 不正確なADMMフレームワーク:
本アプローチの核となるのは、SDP向けに調整された不正確な（inexact）ADMMフレームワークである。標準的なADMMとは異なり、このフレームワークは量子サブルーチンによって導入される誤差を明示的に許容する。

• 双対変数更新: 双対変数 $y$ の更新には、線形システム $(AA^*)y = \dots$ の求解が含まれる。量子設定では、これは量子線形ソルバー（QLS）を用いて解かれる。
• 原始変数更新: 原始変数 $S$ および $X$ の更新には、正定値（PSD）錐への射影が含まれる。古典的には、これには固有値分解が必要となる。QADMMはこれを**多項式近似近接作用素（polynomial proximal operator）**に置き換える。
• 誤差許容: このフレームワークは、ブロックエンコーディング近似、量子特異値変換（QSVT）、および量子状態トモグラフィーによる不正確さを考慮するために、誤差項（$\Delta \tilde{y}, \Delta \tilde{S}, \Delta \tilde{X}$ など）を導入している。著者らは、これらの不正確なスキームの平均イテレートが依然として $\epsilon$-最適解に収束することを証明している。

2. 多項式近接作用素とQSVT:
射影ステップにおける固有値分解のコストを回避するため、著者らは射影作用素 $\text{Proj}_{S_+}(x) = \max(0, x)$ を近似する多項式関数 $g(x)$ を設計している。

• 近似理論を用いて、誤差 $\epsilon$ 以内でReLU関数を近似する次数 $d = O(1/\epsilon)$ の単調増加多項式 $g$ を構築する。
• この多項式は、ブロックエンコーディングモデルの下での**量子特異値変換（QSVT）**を用いて、量子コンピュータ上で実装される。
• 「仮想的な」バリア関数 $h(S)$ が構築されており、その近接作用素はこの多項式変換に対応し、収束解析に必要な変分構造を保証する。

3. アルゴリズムの流れ:
アルゴリズムは以下の手順で反復的に進行する：

1. $y$-更新: 線形写像を古典的に計算し、量子状態を準備し、QLSを用いて線形システムを解く。
2. $V$-更新: 中間変数 $V = C - A^*(y) - \gamma X$ を計算する。これには線形結合としてのユニタリ演算（LCU）を用いる。
3. $S$-更新: QSVTを用いて、$V$ に対して多項式スペクトル変換（PSD射影の近似）を適用し、続いてトモグラフィーによって古典的な行列を再構成する。
4. $X$-更新: $S$-更新と同様に、双対変数 $X$ を更新するために多項式変換を適用する。
5. 古典的後処理: 再構成された行列を、実現可能性を確保するために有界集合（フロベニウスノルム制約）に射影する。

主な貢献

1. 堅牢な不正確ADMMフレームワーク: 本論文は、古典的なADMMの収束理論と実用的な量子計算との間の理論的な架け橋を確立している。量子ノイズや近似限界によって制限される誤差が含まれている場合でも、平均イテレートが $O(1/\epsilon)$ のレートで $\epsilon$-最適解に収束することを証明している。
2. SDPのための多項式近接写像: 著者らは、ADMMにおける固有値分解を多項式固有値変換で置き換える新しい手法を導入した。これにより、QSVTを使用して正定値錐制約を効率的に扱うことが可能となり、古典的なスペクトル射影に伴う $O(n^3)$ や $O(n^4)$ のコストを回避できる。
3. 複雑性分析と比較: 本論文は、QADMMが古典的なADMMや既存の量子ソルバー（QMWUおよびQIPM）と比較して、問題の次元 $n$ に関して有利なスケーリングを実現することを示す厳密な複雑性分析を提供している。

結果と複雑性

著者らは、目的関数の絶対精度 $\epsilon_{abs}$ および実現可能性残差を達成するために必要な総計算複雑性を導出している。

• 反復複雑性: アルゴリズムは $K = O\left(\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ 回の反復を必要とする。ここで $R_X$ および $R_S$ は、最適な原始変数および双対変数のフロベニウスノルムの上界である。
• 総複雑性:
  • 古典的操作: $O\left((s_A + n^2)\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$、ここで $s_A$ は制約行列の非ゼロ要素数である。
  • 量子ゲート複雑性: $\tilde{O}\left( \left[ m\kappa_A^2(1+R_y)^2 + n^2(\kappa_A^2(1+R_y) + R_X) \right] \frac{(R_X + R_S)^3}{\epsilon_{abs}^3} \right)$。
  • ここで、$\kappa_A$ は $AA^*$ の条件数であり、$R_y$ は双対変数のノルムの上界である。

比較:

• 古典的ADMMに対して: QADMMは、次元 $n$ に対するより良い依存性を提供する（各反復における固有値分解や行列積に関連する $O(n^6)$ や $O(n^4)$ の因子を回避できる）。
• QIPMに対して: QADMMは、ニュートンシステムの高い条件数（$\kappa_{newt}$）への依存を回避し、精度依存性において異なるトレードオフを提供する。
• QMWUに対して: QADMMはQMWUと同様の次元依存性を持つが、精度パラメータ $\epsilon_{abs}$ に対する低次依存性（一部の領域で3次 vs 高次）を実現しており、特に解のフロベニウスノルム $\|X^*\|_F$ がそのトレース $\text{Tr}(X^*)$ よりもはるかに小さい場合（例：対角SDP埋め込み）に有利である。

意義と主張

本論文は、大規模なSDPを解くために、QADMMが次元に関する良好なスケーリングを提供することを主張しており、古典的なソルバーが固有値分解のコストによって苦慮する問題において有望な候補であることを示している。

著者らは、自身のアプローチが以下の特性を持つことを強調している：

• 量子的な高速化の統合: 最も計算負荷の高い部分を加速するために、QSVTおよびQLSを効果的に活用している。
• 収束性の保証: 不正確なフレームワークを開発することで、量子的な誤差が最適解への収束を妨げないようにしている。
• 特定の仮定への依存: アルゴリズムは、データアクセスおよび入力行列のブロックエンコーディングのために、多項式サイズのQRAMが利用可能であることを前提としている。著者らはこれを強い仮定であると認め、将来の研究ではこの要件を緩和することに焦点を当てるとしている。

結論として、本アルゴリズムはQRAMの仮定によって制限されているものの、大規模な凸最適化、特に大規模な次元と精度の特定の領域において、古典的な一次手法および他の量子SDPソルバーの両方に対する実行可能な代替案を提供することで、量子コンピューティングの応用における重要な一歩となる。