A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs

技術要約：一般グラフにおける最大重み完全マッチングのための量子スケーリング・アルゴリズム

問題設定
本論文は、整数エッジ重みを持つ一般の無向グラフにおける最大重み完全マッチング（MWPM）問題を扱う。頂点数 $n$、エッジ数 $m$、エッジ重みの最大値を $W$ とするグラフ $G=(V, E)$ が与えられたとき、エッジの重みの総和を最大化する完全マッチング $M$ を見つけることが目的である。多くのグラフ問題（最短経路、最小全域木、二部グラフにおけるマッチングなど）では量子加速が確立されているが、一般グラフにおける整数重みのMWPMは、依然として顕著な例外として残っていた。主な困難は、奇数サイクル（ブロッサム）の処理、および増大パスの探索中に複雑なデータ構造（ブロッサムの層状集合や双対変数）を維持することにある。この問題に対する既知の最良の古典的組合せアルゴリズムは、Duan, Pettie, および Su によるもので、実行時間は $\tilde{O}(m\sqrt{n} \log W)$ である。

手法
著者らは、密な領域（$m \ge n^{3/2}$）において古典的な境界を改善する量子アルゴリズムを提示している。このアルゴリズムは、$O(\log W)$ のスケールにわたる重みスケーリング手法を利用した、Duan, Pettie, および Su による古典的な「LIQUIDATIONIST」フレームワークに基づいている。アルゴリズムは、以下の3つの手続きに分割される：

1. Small Blossom Liquidation（小規模ブロッサムの清算）: 小さな縮約部分グラフを処理する。
2. Free Vertex Reduction（自由頂点の削減）: 増大パスを見つけることで、自由頂点の数を反復的に減少させる。
3. Finalization（最終化）: すべてのスケールが処理された後にマッチングを完了させる。

核心となる革新は、Free Vertex Reduction 手続きを量子サブルーチンである QSEARCHONE に置き換えつつ、他の手続きは古典的なまま維持した点にある。この手続きは、各スケールにつき $\tau$ 回実行される。ここで $\tau$ は調整可能なパラメータである。

主要な技術的貢献

• QRAMモデルの実装: アルゴリズムは、量子ランダムアクセスメモリ（QRAM）モデルで動作し、隣接リスト、双対変数、ブロッサム構造などの古典的なデータ構造へのコヒーレントなアクセスを重ね合わせ状態で可能にする。これにより、入力のロードやデータ構造の更新が実行時間に考慮され、入力へのアクセスを無視した手法を回避している。
• 量子パス探索（QUANTUMPATHSEARCH）: 著者らは、増大パスのための Gabow-Tarjan 深さ優先探索（DFS）を量子設定に適応させた。縮約グラフ $G/\Omega$ を明示的に構築・維持することはコストが高すぎるため、アルゴalaは、各頂点がどのルートブロッサムに属しているかを追跡するための ROOTB 配列を維持しながら、元のグラフ $G$ を探索する。
  • Grover探索: アルゴリズムは、DFS スタック内の現在の頂点に接続する適格なエッジを見つけるために、Grover 型の探索（具体的には BBHT 変種）を使用する。適格性の基準（基準2）は、双対変数とエッジ重みに依存する。
  • ブロッサムの処理: 量子探索は、縮約グラフを明示的に構築することなく、「Grow Events（新しい頂点の発見）」や「Blossom Events（奇数サイクルの検出）」を処理する。ブロッサムが形成される際、アルゴリズムは ROOTB 配列を効率的に更新するために「サイズによる結合（union-by-size）」戦略を使用し、頂点のラベルが最大 $O(\log n)$ 回しか更新されないことを保証する。
• 古典的手続きの代替解析: 著者らは、Small Blossom Liquidation 手続きに関する洗練された解析を提供している。サイズ $\tau$ の小規模ブロッサム内のエッジ数は高々 $\tau^2$ であるという観察に基づき、このステップの境界を、元の $\tilde{O}(\tau m \log W)$ よりもタイトな $\tilde{O}(n\tau^2 \log W)$ として導出している。
• $\tau$ の最適化: 全体の実行時間は $\tau$ の関数となる。著者らは、3つの手続きのコストのバランスをとるためにこのパラメータを最適化している。

結果
提案された量子アルゴリズム QLIQUIDATIONIST は、以下の実行時間を達成する：
$$\tilde{O}(nm^{2/3} \log W)$$
これは、密な領域（$m \ge n^{3/2}$）において、既知の最良の古典的組合せ境界である $\tilde{O}(m\sqrt{n} \log W)$ に対する漸近的な改善である。

実行時間の内訳は以下の通りである：

• Free Vertex Reduction: $\tilde{O}(\tau \sqrt{mn} \log W)$ （$\tilde{O}(\tau m \log W)$ からの量子加速）。
• Small Blossom Liquidation: $\tilde{O}(n\tau^2 \log W)$ （改良された解析）。
• Finalization: $\tilde{O}(\frac{nm}{\tau} \log W)$。
• 古典的オーバーヘッド: $\tilde{O}(m \log W)$。

$\tau = m^{1/3}$ と設定することで、支配的な項は $\tilde{O}(nm^{2/3} \log W)$ となる。論文では、$m = \Theta(n^{3/2})$ の場合、量子と古典の境界は漸近的に等価であるが、$m = \omega(n^{3/2})$ の場合には量子境界の方が厳密に優れていることが記されている。

意義と主張
本論文は、一般グラフにおける MWPM 問題に対して、最良の古典的組合せアルゴリズムを漸近的に上回る、最初の量子アルゴリズムを提示したと主張している。著者らは、彼らの手法が単なる Grover 探索によるグラフ探索の高速化ではなく、古典的なデータ構造（特にブロッサムの層状集合と双対変数の扱い）の大幅な修正と、古典的アルゴリズムの計算量の再解析を必要とするものであることを強調している。

著者らは、自らの改善の範囲について謙虚であり、この高速化は密な領域に特有のものであると述べている。彼らは、PQSEARCH（優先度付きキュー駆動の Edmonds 探索）に依存する Small Blossom Liquidation および Finalization ステップが、残されたボトルネックであると特定している。彼らは、直接的な Grover 探索では PQSEARCH の動的なイベントスケジューリングを容易に置き換えることができないと述べており、イベント管理の量子的な対応物の設計は未解決の問題であるとしている。したがって、本論文はすべての領域における MWPM の普遍的な量子加速を主張するものではなく、むしろ密なケースにおける特定の、証明可能な改善を提示している。