巡回セールスマン問題（TSP）はなぜ難しい？──古典的解法と量子的アプローチ（研究〜一部実用）まで

0. はじめに：ルート最適化について

巡回セールスマン問題（Traveling Salesman Problem; TSP）は、「複数の都市をそれぞれ1回ずつ訪問して出発点に戻る。その総移動距離が最小になる巡回ルートを求めよ」という問題です。
配送・配車・観光周遊・工場内搬送など、さまざまなルート最適化の問題として頻繁に登場します。

⸻

1. 数式で定義するTSP

都市（地点）集合を $V={0,1,\dots,n-1}$、都市間距離（コスト）を $d_{ij}$ とします（対称TSPなら $d_{ij}=d_{ji}$）。

求めたいのは「都市の並び」＝巡回順序です。巡回路（ハミルトンサイクルと言います）を $\pi$ と書くと、目的は次です。
$\min_{\pi}\ \sum_{t=0}^{n-1} d_{\pi(t),\pi(t+1)}\quad(\pi(n)=\pi(0))$

2. 何が難しさの正体か：組合せ爆発

TSPの本質的な難しさは、候補ルート数が爆発的に増えることです。
• 出発点を固定した「有向（順序つき）」巡回：$(n-1)!$
• 対称TSP（逆回り同一）で出発点固定：$(n-1)!/2$

例：
• $n=10$：$(9)!/2=181{,}440$
• $n=20$：$(19)!/2\approx 6.1\times 10^{16}$
• $n=30$：$(29)!/2\approx 4.4\times 10^{30}$

「全部試す（全探索）」がすぐ破綻するのは、この“階乗で増える”候補数のせいです。

⸻

3. 計算量クラスの観点：NP困難（NP-hard）

TSPは「最短巡回路を求める最適化問題」としてNP困難で、判定版（例：「長さ $\le B$ の巡回路は存在するか？」）はNP完全として整理されます。
NP困難（NP-hard）とは「正解を見つけるのは死ぬほど大変だけど、正解かどうかをチェックするのはわりと簡単な問題が集まるクラス」です。

• NP困難（NP-hard）：NP以上に難しいかもしれない難問代表。（※答えの確認が簡単とは限らない）
• NP完全（NP-complete）：
　1. NPに属していて（答えの確認が簡単）
　2. かつNP困難（代表級に難しい）

TSPは
• 「最短を求める」最適化版：NP困難
• 「距離L以下が存在する？」判定版：NP完全
という言い方をします。

⸻

4. 古典（クラシカル）解法：大きく3種類

4.1 厳密解（最適保証あり）

計算量オーダーの意味
「入力サイズ n を大きくしたとき、計算時間が“だいたいどんな増え方をするか”の目安」です。

(a) 全探索
巡回セールスマン問題（TSP）の全探索は、要するに「都市を回る順番」を全部試す方法です。都市が $n$ 個あると、順番の総数（並べ方＝順列）が factorial（階乗）で増えます。
計算量はざっくり $O(n!)$。小さい $n$ 以外は厳しいです。

(b) 動的計画法（Held–Karp）
動的計画法（DP）は、ひとことで言うと 「同じ計算を何度もしないために、途中結果を部分集合としてメモしながら解くやり方」です。“賢い全探索”みたいな立ち位置で、特に「選び方の組合せ」が出る問題に強いです。
部分集合DPを導入することでで計算コストは $O(n^2 2^n)$ まで改善します。階乗よりは良いですが、やはり指数なので $n$ が増えると厳しいです。
まず出発点を 0 に固定します。
DPをこう定義します：

$dp[S][j]$ :
「集合 }Sの都市を全部訪問して、最後が jで終わる最短距離」
ここで
• $S$ は「訪問済み都市の集合」（0を含む）
• $j$ は「最後にいる都市」
です。
最後が $j$ で終わるには、そのひとつ前は $k$ だったはずなので、

$dp[S][j] = \min_{k\in S,\ k\neq j}\Bigl(dp[S\setminus{j}][k] + d_{k,j}\Bigr)$

つまり「最後の一歩」を全部試して、最小を取ります。
都市が $n$ 個あると、都市の集合の取り方（部分集合）は$2^n$個あります（各都市を「入れる/入れない」の2択だから）。

Held–Karp はこの $S$ をいろいろ変えながらDPするので、まずここで $2^n$ が出ます。
$S$ が決まったら、最後の都市 $j$ はだいたい最大で $n$ 通りあります。
なので状態の数はざっくり
$(\text{集合の数})\times(\text{最後の都市}) \approx 2^n \times n$
です。
更新式では$k\in S,\ k\neq j$を全部試して最小を取ります。$k$ の候補も最大で $n$ 通り。
つまり 1状態を計算するのに最大 $O(n)$ かかります。
以上を掛け算して
• 状態数：$2^n \times n$
• 1状態の計算：$O(n)$
だから全体は$(2^n \times n)\times O(n) = O(n^2 2^n)$です。


(c) 分枝限定・カッティングプレーン（商用ソルバー含む）
現実の大規模でも強い手法群。ただし実装は高度で、問題構造（距離の性質）にも依存します。

⸻

4.2 近似解

距離が三角不等式を満たす“メトリックTSP”では、Christofidesの $3/2$ 近似などが有名です。

⸻

4.3 ヒューリスティクス

現場でよく使われるのはここです。
• 局所探索（2-opt, 3-opt, …）
• Lin–Kernighan（LK）系
• 遺伝的アルゴリズム（GA）：個体＝都市の順列として、OX交叉や反転突然変異など“順列を壊さない”操作が重要
• さらに2-optなどを混ぜる（メメティックGA）と強化されやすい

実務の「ルート最適化」はTSPより複雑（時間窓・車両数・休憩・予約枠…）なので、厳密解より“良い近似を速く”が勝ちやすいのもポイントです。

⸻

5. 量子的アプローチ：TSPはどう“量子化”される？

量子的アプローチは古典より「有利になりうる」可能性があります。
古典：候補解を賢く絞りながら探索する。基本は「試した情報しか持てない」
量子：候補解を重ね合わせで同時に持ち、干渉で「良い答えが出やすい分布」を作れる

量子でTSPを扱う代表的ルートは、
1. TSPをQUBO（Quadratic Unconstrained Binary Optimization）に落とす
2. QUBOをIsingハミルトニアン（エネルギー最小化）として解く
3. その解法にQAOAや量子アニーリング（あるいはハイブリッド）を使う

という流れです。
以下にわかりやすい説明をします。
① TSPを「0か1のパズル」に言いかえる（QUBO）
TSPは「どの順番で街を回るのが一番近い？」かとい問題でした。量子コンピュータは、そのままだと扱いにくいから、
“この街をこの順番で行く？” → はい(1) / いいえ(0)
みたいな、0か1で答える大きなパズルに言いかえる。
これが QUBO（クーボ）。

② そのパズルを「山の高さ（エネルギー）」に変える（Ising）
次に、その0/1パズルを正しいルールを守って、距離も短いほど“エネルギーが低い”
ルール違反や遠回りほど“エネルギーが高い”と考える。
一番低いエネルギー＝一番いい答えになるように作る。
これが Ising（イジング）ハミルトニアンと呼ばれる形です。

③ QAOA / 量子アニーリングで最小エネルギーを探索
探し方の代表が2つ：
• QAOA
コストに応じて位相（phase）を回す操作を繰り返していい答えに寄せる方法
• 量子アニーリング
山の上を滑ってできるだけ谷底に落ちる方法
どちらも完全解を必ず見つけるというより、最適解を見つけやすくするやり方です。

⸻

6. QUBOによるTSP定式化（位置エンコーディング）

よく使われるのが「位置（時刻）エンコーディング」です。
$x_{i,t}\in{0,1}\quad(\text{都市 }i\text{ を巡回の }t\text{ 番目に訪れるなら }1)$

6.1 制約（各時刻に都市は1つ、各都市は1回）

各時刻に都市は1つ：$\sum_{i=0}^{n-1} x_{i,t}=1\quad(\forall t)$
各都市は1回：$\sum_{t=0}^{n-1} x_{i,t}=1\quad(\forall i)$

6.2 目的関数（隣接する訪問の距離）

$\min \sum_{t=0}^{n-1}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} d_{ij}x_{i,t}x_{j,(t+1)\bmod n}$

6.3 “Unconstrained”にする（ペナルティ法）

QUBOは「制約なし二次式」なので、制約違反に大きな罰則 $A$ を足します。
$\min\Bigl(\text{目的}\Bigr)+A\sum_t\Bigl(\sum_i x_{i,t}-1\Bigr)^2+A\sum_i\Bigl(\sum_t x_{i,t}-1\Bigr)^2$

ここでのボトルネック：変数数が $n^2$（$x_{i,t}$ が $n\times n$）になること。量子（特にゲート型）では、そのまま量子ビット数に跳ね返りスケールが難しくなります。

⸻

7. QAOAで“量子的に”最適化するとは？

QAOA（Quantum Approximate Optimization Algorithm）は、組合せ最適化を量子回路で近似する枠組みです。
「良い答え（コストが小さい答え）に当たりやすいように、量子状態の偏りをデザインする方法」です。
コストを表すハミルトニアンを $H_C$、混合のハミルトニアンを $H_M=\sum_k X_k$、初期状態を $|+\rangle^{\otimes m}$ とすると、QAOAの状態は次の形で表せます。
$|\boldsymbol{\gamma},\boldsymbol{\beta}\rangle=\prod_{\ell=1}^{p}e^{-i\beta_\ell H_M},e^{-i\gamma_\ell H_C}\ |+\rangle^{\otimes m}$

$p$ は回路の深さです。$(\gamma,\beta)$ は古典最適化で調整します。
QAOAは、最適化問題の各候補解を量子状態の重ね合わせとして持ち、「コストに応じて位相を変える操作」と「候補解どうしを混ぜる操作」を交互にかけることで、干渉を利用して“良い解が出る確率”を高める手法です。層の数 p を増やすと分布を作り込める一方、実機ではノイズの影響も受けます。各層のパラメータ$(\gamma,\beta)$ は、回路を実行して得られた測定結果から期待コストを評価し、古典最適化で更新していく量子＋古典のハイブリッド方式です。

⸻

8. 量子アニーリングとハイブリッド

量子アニーリングは、Ising/QUBOの「エネルギー最小（最適化）」を狙う方式で、TSPをQUBO化して試す研究もあります。ただしTSPは制約が厳しく、QUBOの作り方・ペナルティ設計・問題サイズの増大が効いてきます。

⸻

9. 研究開発と一部実用の現在地（富士通・IBMなど）

9.1 「量子そのもの」より先に進んでいる：量子インスパイアド
量子インスパイアド（quantum-inspired）は、ひとことで言うと 「量子コンピュータ“みたいな発想”で作ったアルゴリズム／専用機だけど、動いているのは量子ではなく古典（クラシカル）計算」です。
富士通はDigital Annealer（量子インスパイアド）で、QUBOに落とした組合せ最適化を解く実用サービスを提供しています。これは“ゲート型量子コンピュータ”ではない一方で、「量子を待たずに今使える最適化」として実務寄りです。

9.2 ゲート型量子コンピュータ
ゲート型量子コンピュータは「量子版のCPU」です。普通のCPUが AND/OR/NOT みたいな“論理ゲート”で計算を組み立てるのと同じで、量子版は 量子ゲートを順番にかけて計算します。こちらは研究開発〜共同利用が広がっている段階です。
IBMなどは耐故障（fault-tolerant）量子計算機に向けたロードマップを掲げ、基盤を積み上げています。

⸻

10. おわりに：ツアー／ルート現場での現実的な見取り図
• 古典の数理最適化＋強いヒューリスティクス（2-opt/LK/GAなど）
• 量子（QAOA/アニーリング）は、TSPをQUBO/Isingに落とせる点で理論的にきれいだが、スケール（変数 $n^2$）と制約取り込みが壁になりやすい
• 一方で、量子インスパイアドやハイブリッドにより「一部実用」の動きは既にあります
• ゲート型量子コンピュータが本番運用のルート最適化の中核になるには、耐故障化・大規模化・運用成熟がもう少し必要になりそうです。

◾️参考文献
基礎（計算量・NP困難）

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.

• Karp, R. M. (1972). “Reducibility Among Combinatorial Problems.” In Complexity of Computer Computations (Proc. Symp., 1972).

• Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall.

TSP（古典アルゴリズム：DP・ヒューリスティクス・実用ソルバ）

• Held, M., & Karp, R. M. (1962). “A Dynamic Programming Approach to Sequencing Problems.” SIAM Journal on Applied Mathematics, 10(1), 196–210.（Held–Karp DP）

• Lin, S., & Kernighan, B. W. (1973). “An Effective Heuristic Algorithm for the Traveling-Salesman Problem.” Operations Research, 21(2), 498–516.（Lin–Kernighan）

• Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.（Concorde等の体系）

• Concorde TSP Solver（公式）

• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” INFORMS Journal on Computing, 3(4), 376–384.（ベンチマーク集）

• Arora, S. (1998). “Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems.” J. ACM 45(5).（ユークリッドTSPのPTAS）

QUBO / Ising（定式化の典型）

• Lucas, A. (2014). “Ising formulations of many NP problems.” Frontiers in Physics, 2:5.（NP問題→Ising/QUBO写像の代表）

QAOA（ゲート型量子：変分近似）

• Farhi, E., Goldstone, J., & Gutmann, S. (2014). “A Quantum Approximate Optimization Algorithm.” arXiv:1411.4028.

• Qiskit Optimization Tutorial: “Max-Cut and Traveling Salesman Problem”（QAOAでMaxCut/TSP例）

• Qiskit Optimization Tutorial: “Converters for Quadratic Programs”（QUBO→Ising等の変換）

• Qiskit Optimization API: to_ising（QuadraticProgram→Ising Hamiltonian）

• IBM Quantum Tutorial: “Quantum approximate optimization algorithm (QAOA)”

量子アニーリング（QUBO/Isingを“エネルギー最小化”とおく)

• D-Wave Systems. (2022). Problem Formulation Guide（Ising/QUBO/BQMの入門と実装観点）

• dwave_networkx.algorithms.tsp.traveling_salesperson（TSPをQUBO化してサンプルする実装の説明）

• Jain, S., et al. (2021). “Solving the Traveling Salesman Problem on the D-Wave Quantum Annealer…” Frontiers in Physics.（TSPをQUBOでアニーリング実験）

量子インスパイアド／実用寄りの古典ハードで“量子的な最適化

• Fujitsu. Digital Annealer（量子インスパイアド最適化の公式説明）

• Fujitsu (CaaS) Digital Annealer User’s Guide（QUBO入力とエネルギー関数の説明）

• Kao, Y.-T., Liao, J.-L., & Hsu, H.-C. (2023). “Solving Combinatorial Optimization Problems on Fujitsu Digital Annealer.” arXiv:2311.05196.

• Toshiba. Quantum-Inspired Optimization Solutions SQBM+（Simulated Bifurcation由来の最適化）

• Microsoft News (Japan). “Toshiba launches SQBM+ … on Azure Quantum” (2022).（SQBM+提供・アルゴリズム概要）

研究開発の現状:量子計算機のロードマップ

• Fujitsu & RIKEN (2025). “develop world-leading 256-qubit superconducting quantum computer.”（256量子ビット開発発表）

• IBM Quantum Blog. “IBM lays out clear path to fault-tolerant quantum computing” （Starling等）

• IBM Quantum Hardware & roadmap（2026/2029目標などの概要）