A quantum central path algorithm for linear optimization

技術要約：線形最適化のための量子中心パス・アルゴリズム

問題設定
本論文は、$\min c^\top x$ s.t. $Ax \ge b, x \ge 0$ という形式の線形最適化（LO）問題、およびその双対問題の解決に取り組んでいる。古典的な内点法（IPM）はこれらの問題を解くための最先端の手法であるが、各反復において大規模な線形システム（ニュートン線形システム）を解く必要がある反復的なニュートンステップに依存している。既存の量子内点法（QIPM）は、このプロセスを加速するために量子線形システムアルゴリズム（QLSA）を用いてこれらの線形システムを解こうと試みている。しかし、現在のQIPMには主に2つの制限がある。(1) 多くの場合、量子ランダムアクセスメモリ（QRAM）モデルを必要とし、これは近未来のデバイスにおいては非現実的であると考えられること。(2) 古典的なIPMの $O(\sqrt{n} \log(1/\varepsilon)$ の反復計算量量を継承しており、古典的な解を抽出するために高価な量子状態トモグラフィに依存していることである。

手法
著者らは、**量子中心パス法（QCPM）**と呼ばれる新しいアプローチを提案している。QIPMが古典アルゴリズムの「ステップ」を量子化するのに対し、QCPMは中心パス自体の「ダイナミクス（動態）」を量子化するものである。その手法は以下の通りである：

1. ハミルトニアン定式化: 著者らは、正の直交領域上で定義された、時間依存のハミルトニアン演算子の族 $H(\mu, h)$ を構築する。このハミルトニアンは、運動エネルギー項とポテンシャルエネルギー項からなるシュレディンガー演算子である：
   $$H(\mu, h) = -\frac{h^2}{2} \nabla^2 + \Phi_\mu(z)$$
   ここで、$\mu$ は中心パスパラメータ（双対性のギャップに関連する）であり、$h$ はプランク定数に類似したスケーリングパラメータとして機能する。ポテンシャル関数 $\Phi_\mu(z)$ は、自己一致障壁関数（具体的には二次継続対数関数）から導出されており、その全域的最小値がLO問題の $\mu$-センターに正確に一致するように設計されている。

2. 基底状態のエンコーディング: 中心的な理論的洞察は、$H(\mu, h)$ の基底状態（最小固有値を持つ固有ベクトル）が、中心パス上に位置する確率分布をエンコードしているという点である。$\mu \to 0$ となるにつれ、この分布は最適解の周囲に集中する。パラメータ $h$ は、この分布の分散を制御する。$h$ を減少させることは、解の周囲に波束を「絞り込む（squeeze）」ことに相当する。

3. 固有パス・トラバーサル（Eigenpath Traversal）: ニュートンステップを反復する代わりに、このアルゴリズムはハミルトニアンの基底状態の軌跡を辿る。著者らは、パラメータ $(\mu, h)$ に対して2段階のスケジュールを採用している：

   • ステージ1（輸送/Transport）: $\mu$ が1から$\varepsilon$へと減少する間、$h = \mu$ とする。これにより、基底状態の中心が中心パスに沿って移動する。
   • ステージ2（絞り込み/Squeezing）: $\mu$ を$\varepsilon$に固定し、$h$ をターゲット値 $h^*$ まで減少させて、$\varepsilon$-最適解の周囲の分布を狭める。
     このスケジュールは、連続する基底状態が大きなオーバーラップ（$> 1/\sqrt{3}$）を持ち、効率的な固有パス・トラバーサル・アルゴリズム（具体的には Boixo, Knill, Somma による手法）の条件を満たすように構成されている。

4. 実装: アルゴリズムは初期基底状態（$\mu=1$ に対応）を準備し、その後、シュレディンガーのダイナミクスをシミュレートしてパスを辿る。空間離散化を利用して、無限次元の演算子をゲート型量子コンピュータに適した有限次元行列にマッピングする。決定的なのは、このアルゴリズムはQRAMを必要とせず、ポテンシャル関数の評価オラクルを介した問題データ $(A, b, c)$ のバイナリ記述へのアクセスのみを必要とする点である。

主な貢献

• 新しいパラダイム: 本論文は、ニュートンステップを量子化するのではなく、シュレディンガーのダイナミクスを通じて中心パスを直接シミュレートすることによってLOを解く、初の量子アルゴリズムを導入している。
• QRAMからの独立: アルゴリズムは標準的なゲートモデルで動作し、QRAMを必要としない。これは、従来のQIPMの提案における主要な実用上のボトルネックに対処している。
• 非反復的な性質: 解は最終的な量子状態を測定することによる「ワンショット」の形式で得られ、反復ループやそれに伴う誤差の蓄積、あるいは繰り返しのトモグラフィの必要性を回避している。
• 理論的保証: 著者らは、ポテンシャル関数の強凸性、ハミルトニアンのスペクトルギャップ、および基底状態の中心パスへの集中に関する厳密な証明を提供している。

結果と計算量
本論文は、QCPMが $m$ 個の制約と $n$ 個の変数を持つLO問題を $\varepsilon$-最適性で解く際の計算量を以下のように確立している：

• クエリ計算量: ポテンシャル関数オラクルに対する $\tilde{O}\left((m + n)^{3/2} \varepsilon^{-1} + (m + n)^{1/2} \varepsilon^{-3/2}\right)$ クエリ。
• ゲート計算量: $\tilde{O}\left(\left[(m + n)^{3/2} \varepsilon^{-1} + (m + n)^{1/2} \varepsilon^{-3/2}\right] \cdot \text{nnz}(A)\right)$ 基本ゲート。ここで $\text{nnz}(A)$ は制約行列の非ゼロ要素数である。

計算量は問題の疎性と精度 $\varepsilon$ に依存するが、注目すべきは問題データの条件数への依存を回避している点である。

意義と主張
著者らは、この研究が「QRAMなしでも、回路モデルにおいてエンドツーエンドの量子加速が実現可能であるという説得力のある証拠を提供する」と主張している。彼らは、QCPMが、従来のQIPMのような「量子サブルーチン」のアプローチとは異なる、量子最適化の新しいパラダイムを提供することを強調している。

論文は、現在の立ち位置について以下のように控えめに述べている：

• リソース分析によれば、アルゴリズムは理論的には健全であるが、近未来のデバイスで実用化するためには（特に誤差依存性に関して）大幅な強化が必要である可能性がある。
• アルゴリズムは、LOの直接的な問題ではなく、LOの「自己双対埋め込みモデル」を解くものである（これは古典的なIPMにおける標準的な理論的手法である）。ただし、著者らは古典的な手法で使用される終了判定もここに応用できると考えている。
• フレームワークは有望であり、既知の直接的な古典的対応物を持たないが、本論文は即座の実用的な優位性を主張するのではなく、厳密な分析のための「基礎」を築くものである（現在の最良の古典的アルゴリズムは $\tilde{O}((m+n)^\omega)$ の時間で動作する）。
• 著者らは、変動するポテンシャルの全域的最小値を追跡する古典的なシステムを設計することが極めて困難であることを認め、古典的なダイナミカルシステムの構築を試みていないことを明記している。

要約すると、本論文は、内点法と量子ハミルトニアンシミュレーションを結びつける理論的なブレイクスルーを提示しており、QRAMの制限を回避しながら線形最適化に対する量子加速への経路を提供するものである。