量子コンピューティング開発企業Rigetti ComputingとPurdue Universityの研究者らは、Rigettiの量子プリコンディショニング・フレームワークをハード制約付き組合せ最適化問題へと拡張する共同研究を発表した。浅いQuantum Approximate Optimization Algorithm（QAOA）回路から抽出した2点変数相関を用いて商用Mixed-Integer Programming（MIP）ソルバーの目的関数を修正することで、研究チームは量子プリコンディショニングが古典的なbranch-and-bound探索を導き、プリコンディショニングなしの実行と比較して最大100倍高速に準最適解の閾値へ到達できることを実証した。
| [ Rigetti & Purdue 量子プリコンディショニング・アーキテクチャ ] | ||
|---|---|---|
| 量子特徴抽出 | 古典MIPソルバーとの統合 | ベンチマーク性能とスケーリング |
| • QAOA 2点相関（Zij） | • 元のハードなバランス制約を維持 | • 準最適閾値（ε = 0.01）へ約100倍高速に到達 |
| • 目的関数行列の再構成（Wij → Zij） | • 商用MIPソルバー（Gurobi）で解決 | • 浅い深さ（p = 1）で主要な高速化を実現 |
| • ソフト制約ペナルティ（ρ）のチューニング | • 元のコスト関数でインカンベントを評価 | • スケーリングにおけるフィッティング済み指数関数の底を低減 |
並列科学計算のためのグラフ分割やロジスティクスのルーティングなど、ハード制約下での組合せ最適化はNP困難であり続けており、Gurobiのような厳密な古典ソルバーは膨大な探索木を辿らざるを得ない。この量子プリコンディショニング・フレームワークは、ゲート方式のQPUを単独のソルバーとしてではなく、構造学習のための前処理装置として利用する：
- 相関行列の生成：このアルゴリズムは問題グラフに対して浅いQAOA回路を実行し、コストハミルトニアン内でバランス制約をソフトなペナルティパラメータ（ρ）として課す。得られた量子状態を測定することで、ペアごとの決定変数の整合性を捉えた2点相関行列（Zij）が得られる。
- ハード制約付きMIPの実行：相関行列は目的関数において元のエッジ重み行列（Wij）を置き換える。続いてGurobiは、元のバランス制約を明示的かつ妥協のないハード制約として課しつつ、このプリコンディショニングされた問題を解く。
- インカンベント発見の高速化：コールバックの軌跡データによれば、プリコンディショニングされた目的関数により、古典ソルバーのbranch-and-boundアルゴリズムはより良い分岐判断を下せるようになり、探索プロセスのかなり早い段階で高品質な実行可能解を発見できるようになる。
50個の密な全結合グラフインスタンス（n = 40）にわたって評価した結果、このフレームワークによりGurobiは1秒未満でベースラインの大域的最適値の1%以内の解に到達できた——これはプリコンディショニングなしの実行では数時間を要するのと対照的である。特筆すべきは、プリコンディショニングによる利点の大部分がp = 1で得られたことであり、これにより回路の深さと量子ゲートノイズへの曝露が最小限に抑えられた。問題規模のスケーリングに伴う高コストな変分最適化を回避するため、研究チームはn = 20で最適化した再スケール済みQAOAパラメータ（γℓ ∝ 1/√n）を、性能を損なうことなくより大規模なグラフインスタンスへと転用することに成功した。
arXiv上の完全な研究論文（arXiv:2608.28842）はこちらからご覧いただけます。
2026年9月2日
