A Hybrid Classical-Quantum Annealing Algorithm for the TSP

本論文は、グラフ縮約を用いて問題の次元を削減し、D-Wave アニーラーなどの現在の量子デバイス上で効率的に解を導出することを可能にする、巡回セールスマン問題のためのハイブリッド古典・量子アニーリングアルゴリズムを提案するものであり、その性能は古典シミュレーションおよび量子ハードウェアの両方を通じて検証されている。

要約

あなたがクライアントのために完璧なロードトリップを計画しようとする旅行代理店だと想像してください。クライアントが訪れたい1,000都市のリストがあり、すべての都市をちょうど一度ずつ訪れて自宅に戻る、単一の最短経路を特定する必要があります。これが有名な「巡回セールスマン問題（TSP）」です。

問題は、都市の数が増えるにつれて、可能な経路の数が爆発的に増加し、世界の最も強力なスーパーコンピューターさえも、絶対的に最良の経路を見つけようとして行き詰まってしまうことです。それは、毎秒大きくなり続ける砂浜から、特定の砂粒を見つけようとするようなものです。

この論文は、古典的コンピューター（現在私たちが使用しているもの）と量子コンピューター（未来的で実験的なもの）という二つの世界の最良の側面を組み合わせることで、このパズルを解決する巧妙な「チームワーク」戦略を提案しています。

以下に、彼らの手法がどのように機能するかを、簡単な比喩を用いて説明します。

1. 問題：選択肢が多すぎる

TSP を巨大で絡み合った毛糸の玉だと考えてください。一度に全体をほどこうとすれば、それは不可能です。現在の量子コンピューターは、小さく繊細な手のようなものです。非常に強力ですが、一度に握れる毛糸の断片はごくわずかです。1,000 都市という全体の玉を扱うことはできません。なぜなら、すべてを掴むのに十分な「指」（量子ビット）や、適切な接続がないからです。

2. 解決策：「確信ある骨格」

著者たちの秘密の武器は、「グラフ縮小（Graph Contraction）」と呼ばれる技術です。500 人の旅行代理店のグループがいて、それぞれが 1,000 都市のための良い経路のアイデアをスケッチしていると想像してください。

• プール: これら 500 枚のスケッチをすべて集めます。
• パターン: 地図を注意深く見ます。ほぼすべてのスケッチで、代理店たちは都市 A と都市 B を、都市 C と都市 D を接続すべきだと同意していることに気づきます。これらが「確信ある」接続です。
• ショートカット: すべての都市を別々の停留所として扱うのではなく、その合意された接続を「接着」します。都市の長い鎖（A-B-C-D）を、単一の巨大な「メガ都市」に変えるのです。

これを行うことで、目的地を変えるのではなく、単に地図を単純化していることになります。1,000 都市の問題を 50 都市の問題に変えるかもしれません。これが「縮小」です。

3. 量子ステップ：「魔法のコンパス」

これで地図を管理可能なサイズ（例えば 50 都市）に縮小したら、この小さなパズルを「量子アニーラー」（彼らが使用した D-Wave 機械のようなもの）に渡します。

• 古典的コンピューターは通常、一つ経路を試して行き詰まり、別の経路を試すという方法でこれらのパズルを解きます（迷路の中のネズミのようなものです）。
• 量子コンピューターは「量子トンネル効果」と呼ばれる現象を利用します。迷路にネズミが立ち往生する深い谷があると想像してください。量子コンピューターは、谷の壁を貫通して反対側の出口を見つけることができる幽霊のようなものです。

著者たちは、この量子の「幽霊」能力のシミュレーション（パス積分モンテカルロ法と呼ばれるもの）を使用して、縮小された小さな地図の最良の経路を見つけました。地図が十分に小さくなったため、量子コンピューターは実際にそれを効率的に解くことができました。

4. 結果：組み立て直す

量子コンピューターが「メガ都市」の最良の経路を見つけると、アルゴリズムはそれらを「剥がし」、経路を元の 1,000 都市に展開します。「接着」された部分は、当初見出された最も信頼できる接続であったため、最終的な経路は完璧な解に非常に近くなります。

彼らは何を見つけましたか？

チームは、実世界の旅行データ（TSPLIB というライブラリから）でこれをテストしました。

• 小規模な旅: 都市の小さなグループについては、彼らの手法は毎回完璧な経路を見つけました。
• 大規模な旅: 1,000 都市以上の大規模な旅については、問題を量子コンピューターが処理できるサイズまで縮小することに成功しました。結果として得られた経路は非常に良好でした（通常、完璧な距離の 2〜4% 以内）であり、量子コンピューターだけで全体を解こうとするよりも大幅な改善でした。
• トレードオフ: 彼らは、都市を多すぎると接着しすぎると（攻撃的すぎると）、間違いを犯すリスクがあることを発見しました。逆に、少なすぎると量子コンピューターは依然として圧倒されてしまいます。彼らは最良の結果を得るために、「ジャスト・ミート（Goldilocks）」のしきい値を見つける必要がありました。

結論

この論文は、これがすべての旅行問題を瞬時に解決すると主張しているわけではありません。代わりに、今日の限られた量子コンピューターを実用的に利用する方法を示しています。まず古典的コンピューターを使って地図を「単純化」するという重労働を行い、その後、管理可能なパズルを量子マシンに引き渡します。量子マシンは、その特別な「トンネル効果」の力を使って、ほぼ完璧な答えを見つけます。これはハイブリッドなチームであり、古典的コンピューターが調整役として働き、量子コンピューターが最後の難解な部分の専門家として機能します。

技術概要

技術的概要：TSP に対するハイブリッド古典・量子アニーリングアルゴリズム

問題定義

巡回セールスマン問題（TSP）は、完全重み付きグラフにおける最短ハミルトン閉路の特定を必要とする基本的な NP 困難最適化問題である。正確な古典ソルバー（例：Concorde）は大規模なインスタンスを処理できるが、多項式時間におけるスケーラビリティにしばしば苦しむ。一方、量子アプローチ、特に量子アニーリング（QA）は、局所最小値からの脱出に対する熱雑音の有望な代替メカニズムを提供する。しかし、現在のノイズあり中規模量子（NISQ）デバイス、例えば D-Wave アニーラーは、量子ビット数とトポロジカル接続性に関する深刻な物理的制限に直面している。これらの制約は、密な接続性を必要とする大規模 TSP インスタンスを、既存の量子処理ユニット（QPU）に直接マッピングすることを妨げている。

手法

著者らは、大規模 TSP インスタンスと現在の量子ハードウェアの能力の間のギャップを埋めるハイブリッド古典・量子アルゴリズムを提案する。このアプローチは、量子アニーリングの経路積分モンテカルロ（PIMC）シミュレーションと部分 QUBO 抽出戦略という 2 つの基礎的な手法を統合する。

1. 辺の頻度によるグラフ縮小

核心的な革新は、元の問題の次元を削減するグラフ縮小技術である。

• プール生成: アルゴリズムは、2-opt 移動を用いたシミュレーテッドアニーリング（SA）で洗練されたランダム順列を用いて、候補解のプール（$P$）を初期化する。
• 確信度の高いバックボーンの特定: プール全体を分析する代わりに、アルゴリズムは解全体に現れる辺の頻度を計算するために部分集合（$S$）をサンプリングする。信頼度閾値（$\tau$）以上の頻度で現れる辺は、「確信度の高いバックボーン」として特定される。
• 縮小: これらの高頻度辺は固定され、接続されたノードは「スーパーノード」にマージされる。これにより、元のグラフ $G$ は、はるかに小さな部分 TSP インスタンス（$G_{sub}$）に変換される。部分問題の距離行列は、スーパーノードの論理的なマージ（スーパーノードの頭と尾）を考慮して再計算される。

2. ハイブリッド最適化ループ

アルゴリズムは反復ループで動作する。

1. 洗練: 古典的ヒューリスティックが解プールを洗練し、辺の頻度の信頼性を向上させる。
2. サンプリングと縮小: 解の部分集合がサンプリングされ、固定される辺を決定してグラフを縮小する。
3. 量子ソルビング: 縮小された部分 TSP が量子ソルバーを用いて解かれる。本論文の実験では、以下を通じて実装された。
   • 古典シミュレーション: Martoňák らの方式に基づく経路積分モンテカルロ（PIMC）。これは、2-opt 移動を運動エネルギー演算子として用いて、TSP を制約付きイジング様システムにマッピングする。
   • ハードウェア実行: D-Wave Advantage_system 4.1 QPU 上での直接実行。
4. 展開と更新: 部分問題の解は、固定された辺を再挿入することによって元のグラフへ展開される。新しい巡回路がプールに追加され、改善が見つかればグローバル最良が更新される。
5. 終了: 過程は、$K$ 回の連続する反復で改善が見られないまで繰り返される。

主要な貢献

• スケーラブルなハイブリッドフレームワーク: 本論文は、大規模 TSP インスタンスを現在のハードウェアで管理可能なサイズに削減することにより（例：1,002 都市のインスタンスを約 185 ノードに削減）、NISQ デバイスの量子ビット数と接続性の制限を回避する手法を導入する。
• PIMC と部分 QUBO の統合: この研究は、複雑なエネルギー地形のナビゲーションに効果的な PIMC 量子トンネリングの理論的有望性と、反復的な問題分割という実用的な必要性である部分 QUBO 抽出とを組み合わせる。
• ハードウェア上での実証的検証: 著者らは D-Wave 量子アニーラー上でアルゴリズムを成功裏に実証し、縮小戦略が、そうでなければ扱いにくい TSP 部分問題の直接埋め込みを可能にすることを示した。

実験結果

アルゴリズムは、14 から 11,849 都市までの TSPLIB インスタンスで評価された。

• パラメータ感度:
  • 閾値（$\tau$）: $\tau$ を低下させると圧縮率が高まり（問題サイズが減少する）、しかし最適でない辺を固定するリスクが高まり、最適性ギャップが増大する。$\tau=0.75$ の閾値は、中規模インスタンスにとって好ましいバランスを提供した。
  • プールサイズ（$N_I$）とサンプルサイズ（$N_S$）: 500 のプールサイズと 250（50%）のサンプルサイズは、中規模から大規模のインスタンスに対して最良の結果をもたらした。これは、確率的サンプリングが辺の選択が過度に決定論的になるのを防ぐことを示唆している。
• 古典的ベースラインとの性能比較:
  • 小規模インスタンス（例：burma14, ulysses22）において、アルゴリズムはグローバル最適解（0% ギャップ）を見つけた。
  • 大規模インスタンス（例：pr2392）において、アルゴリズムは平均最適性ギャップを 4% 未満に維持し、いくつかのケースで Google の OR-Tools を上回った（例：rl11849 は 7.36% ギャップに対し、OR-Tools は 14.58%）。
• D-Wave ハードウェアの結果:
  • D-Wave QPU 上で実行された際、ハイブリッドアプローチは、D-Wave ネイティブの BQM ハイブリッドソルバーよりも著しく優れた最適性ギャップを達成した。例えば、ulysses22 において、提案手法は約 5 ノードのみの部分問題を解くことで 2.57% のギャップを達成し、ハイブリッドソルバーの 16.88% と比較した。
• ボトルネック:
  • PIMC シミュレーション段階が、古典シミュレーションにおける主要な計算ボトルネックとして特定された。
  • 非常に大規模なインスタンス（例：rl11849）では、古典的オーバーヘッド（プール初期化と洗練）が支配的となり、実行時間の約 70% を占めた。これは、極端なスケールにおいて古典的前処理コストが量子加速の恩恵を現在相殺していることを示唆している。

意義と主張

本論文は、そのハイブリッド手法が現在の量子デバイスの物理的制限を効果的に緩和すると主張する。グラフを縮小するために古典的最適化を活用することで、著者らは以下を実証する。

1. 実現可能性: 大規模 TSP インスタンスは、高品質な解に必要な構造的完全性を失うことなく、NISQ アニーラーへの埋め込みに適した規模に削減可能である。
2. 量子優位性の可能性: 現在の PIMC シミュレーションは古典的であるが、このフレームワークは量子ハードウェアに直接適応可能に設計されている。結果は、PIMC ステップが量子アニーラー上で実行されれば、計算コストが劇的に削減され、最適化段階に対して潜在的に指数関数的な高速化を提供しうることを示唆している。
3. 堅牢性: この手法は、さまざまなインスタンスサイズにわたって堅牢であり、小規模問題では正確な解を達成し、古典的ヒューリスティックが苦しむ大規模問題では低い最適性ギャップを維持する。

著者らは、古典的オーバーヘッドが巨大なインスタンスにとっては依然として課題であるが、提案された縮小戦略が TSP を現在の量子アニーリング技術の範囲内に成功裏に引き込み、組み合わせ最適化に対するハイブリッド古典・量子アプローチの実用性を検証したと結論づけている。