Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

技術要約：MILPを解くためのハイブリッド量子・古典エンドツーエンド・パイプライン

問題提起
混合整数線形計画問題（MILP）は、物流やサプライチェーン管理などの影響力の大きい意思決定において中心的な役割を果たしているが、その組合せ的性質により計算上の課題が多い。Benders分解（BD）のような分解手法は、マスター問題（MP）とサブ問題（SP）を分離することで大規模なMILPを解くために広く用いられているが、収束の遅さが課題となる。この収束は、マスター問題に追加する「カット」（制約）の選択がいかに有益であるかに決定的に依存する。先行研究において、Paterakis [1] は、このカット選択ステップを最小集合被覆問題として定式化し、量子アニーリングを用いて加速させる手法を提案した。しかし、量子アニーリングは、スケーリングの際に大きなオーバーヘッドをもたらすコストの高いマイナー・エンベディング（minor-embedding）手順を必要とする。

手法
本論文は、Multiple Cuts via Multiple Solutions (MCMS) Benders分解アプローチを拡張した、エンドツーエンドのハイブリッド量子・古典最適化フレームワークを提示する。核心となる革新は、量子アニーリングによるステップを、ゲート型量子近似最適化アルゴリズム（QAOA）の実装に置き換えた点にある。

フレームワークの動作は以下の通りである：

1. MCMS Benders分解: アルゴリズムは、各イテレーションごとに複数の候補解を生成し、複数のサブ問題を並列に解くことで、候補カットのプールを作成する。
2. QUBOとしてのカット選択: カットが過剰になることでマスター問題が計算負荷の高いものになるのを防ぐため、情報の有用なカットのサブセットを選択する。これは最小集合被覆問題として定式化され、次いで二次無制約バイナリ最適化（QUBO）インスタンスへとマッピングされる。
3. QAOAの統合: 前述のアニーリングベースの手法とは異なり、本フレームワークはQAOAを用いてこのQUBOを解く。このパイプラインは、以下の3つの異なるソルバーとインターフェースを持つ：
   • FermioniqのAva：テンソルネットワーク回路エミュレータ。
   • MPS-JuliQAOA：Juliaで構築されたオープンソースの行列積状態（MPS）エミュレータ。
   • IBM Quantum：超伝導量子ハードウェア（IBM Eagleプロセッサ）への直接実行。
4. ケーススタディ: 本フレームワークは、典型的な物流最適化問題である車両ルート計画問題（VRP）を用いて評価される。研究では、パイプラインの実現可能性をテストするために、QOptLibの標準ベンチマーク（顧客20、車両4）およびランダムなトイ・インスタンス（顧客5）を利用している。

主な貢献

• ゲート型への拡張: 本論文は、既存のHQC-MCMSフレームワークを量子アニーリングからゲート型量子コンピューティングへと拡張し、テンソルネットワーク・エミュレータおよび超伝導量子プロセッサの両方での実行を可能にした。
• エンドツーエンドの実装: 著者らは、QAOAサブルーチンを古典的なBenders分解ループに統合した、完全に機能するパイプラインを実証することに成功した。
• 経験的ベンチマーキング: 本研究は、VRPインスタンスにおける異なるソルバー・バックエンド（古典的Cbc、MPS-JuliQAOA、Fermioniq、およびIBM Quantum）に対するパイプラインの性能の比較分析を提供している。

結果
実験結果は、この特定の文脈における現在の量子優位性の実現可能性に関して、いくつかの重要な洞察を提示している：

• 古典的性能: 完全な古典的設定（カット選択にCbcを使用）において、パイプニラインは20顧客のVRPインスタンスに対して実行可能な解を見つけることに成功し、イテレーションが進むにつれて最適性ギャップが減少した。マルチカット・アプローチ（より多くのサブ問題を使用）は、より少ないイテレーションで実行可能な解を導いた。
• 実行時間のボトルネック: 古典的パイプラインの分析により、カット選択ステップが全イテレーション時間のわずかな部分しか消費していないことが明らかになった。計算時間の大部分は、マスター問題を解くことに費やされている。
• 量子性能: トイ問題に対してQAOA（MPS-JuliQAOAを使用）を用いてカット選択ステップを置き換えた際、総実行時間は古典的アプローチと比較して大幅に増加した。研究によれば、このスケールにおいては、MPS-JuliQAOAは最小集合被覆問題に対して古典的ソルバーCbcよりもはるかに効率が低い。
• QAOAの出力: 量子ハードウェアおよびエミュレータを用いた実験では、テストされた構成において、QAOAのサンプルの大部分が実行不可能な解（すなわち、有効な集合被覆を形成しないもの）となった。より深い回路（$p=3$）は、浅い回路（$p=1$）よりも最適なコストのサンプルを生み出したが、全体的な性能は古典的手法を上回らなかった。

意義と主張
本論文は、フレームワークの現状について控えめな評価を下して結論づけている。著者らは、テストされた問題サイズおよび構成においては、量子優位性は期待薄であると明示的に述べている。主な理由は二点ある：

1. 量子的加速の対象であるカット選択ステップは、現在の古典的MCMSパイプラインにおいて計算上のボトルネックにはなっておらず、マスター問題の解決が実行時間を支配していること。
2. 特定の最小集合被覆インスタンスにおいて、古典的ソルバー（Cbc）がQAOAの実装を圧倒していること。

著者らは、本パイプラインは技術的に機能しており、量子強化最適化への再現可能な一歩を示しているものの、集合被覆問題をQUBOへ変換することによって相当なオーバーヘッドが生じると強調している。彼らは、将来の研究において、カット選択ステップがより重大なボトルネックとなり得る、より大規模なベンチマーク、およびより強力な量子プロセッシングユニット（QPU）が価値を提供し得る規模に焦点を当てる必要があると主張している。本研究は、実用的な中小規模のインスタンスにおいて、現在の量子手法がこの特定の分解ステップに対してスピードアップを提供できていないことを示す、経験的な警告的分析として機能している。