2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

現実世界を動かす技術をシェアしよう！～身近なものづくりから最先端テクノロジーまで大募集！～
@harrowharrow16(harrow 16)

IBM Bobを使って、量子コンピュータで「巡回セールスマン問題」を解いてみる

2
Posted at

はじめに

みなさん、こんにちは。IBM Bob + IBM Quantum の第4弾です。今回は、「巡回セールスマン問題」にチャレンジしてみます。

「全国の支社を一番効率よく回るルートって何?」──これを巡回セールスマン問題 (TSP: Traveling Salesman Problem) といいます。都市数が増えると総当たりで解くのは現実的に不可能で、古典コンピュータでも難しいNP困難問題として知られています。

今回はこの問題を IBM Quantum Platform の量子コンピュータ上で動く QAOA (Quantum Approximate Optimization Algorithm) で解いてみます。「量子コンピュータが役立つ問題って何?」という疑問への、具体的な回答になれば嬉しいです。

この記事でやること

  • 巡回セールスマン問題を QUBO という量子コンピュータが扱える形に変換する
  • 変換した問題を QAOA という量子アルゴリズムで解く
  • IBM Quantum Platform 実機で実行する方法を説明する
  • 古典ソルバーと結果を比較する

IBM Quantum の無料アカウントと Python があれば誰でも試せます。

※.量子コンピュータの実機を使うためには、IBM IDとIBM Quantum Platformへのユーザー登録（無料）が必要となります。

コードは GitHub に公開しています:

巡回セールスマン問題とは?

N個の都市をすべて1回ずつ訪れて出発地に戻るとき、総移動距離を最小にするルートを求める問題です。

たとえば4都市の場合、全ルート数は (4-1)! / 2 = 3通り ですが、20都市になると約 6京通り。スーパーコンピュータでも全探索は無理です。

{C8D2A818-DF4C-43D2-93B5-5715CFBD64DF}.png

東京 → 名古屋 → 大阪 → 京都 → 東京  ← このルートが最短?
東京 → 京都 → 大阪 → 名古屋 → 東京  ← こっちのほうが短い?

QAOA とは?

QAOA (Quantum Approximate Optimization Algorithm) は、2014年に Farhi らが提案した量子アルゴリズムです。「近似最適化」の名前の通り、最適解に近い解を高速に求めることを目的としています。

仕組みをざっくり説明

  1. 「コスト回路」と「ミキサー回路」を交互に重ねた量子回路を作る
  2. それぞれの回路の「強さ」(γ と β というパラメータ) を調整する
  3. 量子ビットを測定して、最もコストが低くなるパラメータの組み合わせを探す
  4. 古典コンピュータがパラメータを更新し、量子コンピュータで再測定を繰り返す

{31025D65-C550-42AE-BA00-888D1C59DAD3}.png

QAOA の「層数 p」を増やすほど精度が上がりますが、必要な量子ビット数や回路の深さも増えます。

[ 初期化 ] → [ コスト回路(γ₁) ] → [ ミキサー回路(β₁) ] → ... → [ 測定 ]
                                  ↑ p 層繰り返す

なぜ量子コンピュータが有利なのか?

量子ビットは「重ね合わせ」によって 0 と 1 を同時に保持でき、多数の組み合わせを並列探索できます。これが QAOA が組み合わせ最適化問題に向いている理由です。

QUBO変換 — 問題を量子コンピュータ向けに変換する

量子コンピュータは「0か1か」の変数しか扱えません。そのため TSP を QUBO (Quadratic Unconstrained Binary Optimization) という形式に変換します。

変数の定義

変数 x[都市i][順番p] を次のように定義します:

x[i][p] = 都市 i を p 番目に訪れる場合は 1、そうでなければ 0

4都市の場合、合計 4×4 = 16個の変数が必要です。

制約条件

制約 意味
各都市は1回だけ訪れる x[東京][1] + x[東京][2] + x[東京][3] + x[東京][4] = 1
各順番に都市を1つだけ割り当てる x[東京][1] + x[名古屋][1] + x[大阪][1] + x[京都][1] = 1

この制約に違反した解は「ペナルティ」として大きなコストを課すことで、制約違反を自動的に排除します。

コスト（移動距離）の表現

「i番目に都市A → i+1番目に都市B」という連続する訪問のコストは、距離 dist(A,B) × x[A][i] × x[B][i+1] で表します。これをすべての都市ペア・すべての順番の組み合わせで足し合わせたものが最小化すべき目的関数になります。

実装コード

セットアップ

pip install qiskit qiskit-ibm-runtime qiskit-optimization qiskit-algorithms numpy matplotlib

IBM Quantum への接続

実機実行時は --api-key 引数で API Key を渡します。IBM Quantum Platform の マイアカウントページ で取得できます。

python src/tsp_qaoa.py --mode ibmq --api-key YOUR_API_KEY

QUBO 変換 (tsp_qaoa.py 抜粋)

from qiskit_optimization import QuadraticProgram
from qiskit_optimization.converters import QuadraticProgramToQubo

def build_tsp_qubo(dist_matrix, penalty=10.0):
    n = len(dist_matrix)
    qp = QuadraticProgram(name="TSP")

    # 変数: x[i][p] = 都市 i を p 番目に訪れるか?
    for i in range(n):
        for p in range(n):
            qp.binary_var(name=f"x_{i}_{p}")

    # 目的関数: 移動距離の合計を最小化
    quadratic = {}
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            for p in range(n):
                q = (p + 1) % n
                key = (f"x_{i}_{p}", f"x_{j}_{q}")
                quadratic[key] = quadratic.get(key, 0.0) + dist_matrix[i][j]
    qp.minimize(quadratic=quadratic)

    # 制約1: 各都市を1回だけ訪れる
    for i in range(n):
        qp.linear_constraint(
            linear={f"x_{i}_{p}": 1 for p in range(n)},
            sense="==", rhs=1
        )

    # 制約2: 各順番に1都市だけ
    for p in range(n):
        qp.linear_constraint(
            linear={f"x_{i}_{p}": 1 for i in range(n)},
            sense="==", rhs=1
        )
    return qp

古典ソルバー — ベースラインとして厳密解を求める

QAOA の解が正しいかどうかを検証するため、まず古典ソルバーで厳密な最適解を求めます。

NumPyMinimumEigensolver は QUBO ハミルトニアンを密行列に展開し、NumPy で全固有値・固有ベクトルを計算して最小固有値に対応する解ビット列を返します。つまり「すべての組み合わせを同時に計算する」総当たりに相当します。

特性 内容
手法 全固有値分解（厳密解）
計算量 指数的（変数数が増えると急激に遅くなる）
用途 小規模問題での QAOA 精度検証
使用ライブラリ qiskit_algorithms.NumPyMinimumEigensolver

4都市（16変数）程度なら一瞬で厳密解が得られます。

from qiskit_algorithms import NumPyMinimumEigensolver
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit_optimization.converters import QuadraticProgramToQubo

def solve_classical(qp):
    qubo = QuadraticProgramToQubo().convert(qp)

    solver = NumPyMinimumEigensolver()
    result = MinimumEigenOptimizer(solver).solve(qubo)
    return result

QAOA 実行 (シミュレーター)

from qiskit_algorithms.minimum_eigensolvers import QAOA
from qiskit.primitives import Sampler
from qiskit_algorithms.optimizers import COBYLA
from qiskit_optimization.algorithms import MinimumEigenOptimizer

def solve_qaoa_simulator(qp, reps=2):
    converter = QuadraticProgramToQubo()
    qubo = converter.convert(qp)

    sampler = Sampler()           # ローカルシミュレーター
    optimizer = COBYLA(maxiter=300)
    qaoa = QAOA(sampler=sampler, optimizer=optimizer, reps=reps)

    result = MinimumEigenOptimizer(qaoa).solve(qubo)
    return result

IBM Quantum 実機での実行

待ちジョブ数が最少のバックエンドを自動選択する select_least_busy_backend() を用意しています。api_key 引数を渡すと保存済み認証より優先して使用します。

新しい qiskit-ibm-runtime（2024年3月以降）では、実機に投入する回路がバックエンドの ISA（Instruction Set Architecture）に準拠している必要があります。また、Open プランでは Session が使用できないため、SamplerV2 にバックエンドを直接渡す方式を採用しています。

from qiskit_ibm_runtime import QiskitRuntimeService, SamplerV2 as Sampler, SamplerOptions
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager


class _TranspilingSampler:
    """実機投入前に ISA 準拠のトランスパイルを行う Sampler ラッパー。"""

    def __init__(self, backend, shots: int):
        options = SamplerOptions()
        options.default_shots = shots
        self._inner = Sampler(backend, options=options)
        self._backend = backend

    def run(self, circuits, **kwargs):
        pm = generate_preset_pass_manager(optimization_level=1, backend=self._backend)
        # circuits は QuantumCircuit のリスト、または (circuit, params, ...) の PUB タプルのリスト
        transpiled = []
        for item in circuits:
            if isinstance(item, tuple):
                transpiled.append((pm.run(item[0]),) + item[1:])
            else:
                transpiled.append(pm.run(item))
        return self._inner.run(transpiled, **kwargs)


def select_least_busy_backend(min_qubits: int = 16, api_key: str | None = None) -> str:
    """稼働中かつ pending_jobs が最少の実機バックエンド名を返す。"""
    service = QiskitRuntimeService(channel="ibm_quantum_platform", token=api_key) if api_key else QiskitRuntimeService()
    candidates = [
        b for b in service.backends(simulator=False, operational=True)
        if b.num_qubits >= min_qubits
    ]
    best = min(candidates, key=lambda b: b.status().pending_jobs)
    return best.name


def solve_qaoa_ibmq(qp, reps=1, shots=1024, min_qubits=16, api_key=None):
    backend_name = select_least_busy_backend(min_qubits=min_qubits, api_key=api_key)
    service = QiskitRuntimeService(channel="ibm_quantum_platform", token=api_key) if api_key else QiskitRuntimeService()
    backend = service.backend(backend_name)

    qubo = QuadraticProgramToQubo().convert(qp)

    sampler = _TranspilingSampler(backend, shots=shots)
    qaoa = QAOA(sampler=sampler, optimizer=COBYLA(maxiter=100), reps=reps)
    result = MinimumEigenOptimizer(qaoa).solve(qubo)
    return result

注意点

  • channel="ibm_quantum" は廃止。"ibm_quantum_platform" を使用する。
  • Open プランでは Session は使用不可（有料プラン専用）。
  • 実機に投入する回路は必ず generate_preset_pass_manager でトランスパイルすること。

実行コマンド

# シミュレーターで実行 (デフォルト)
python src/tsp_qaoa.py

# IBM Quantum 実機で実行 (バックエンドは自動選択)
python src/tsp_qaoa.py --mode ibmq --api-key YOUR_API_KEY

# オプション指定
python src/tsp_qaoa.py --mode ibmq --api-key YOUR_API_KEY --reps 1 --shots 2048

実行結果

4都市 (東京・名古屋・大阪・京都) で実行した結果です。

都市数: 4
都市名: ['東京', '名古屋', '大阪', '京都']

距離行列:
[[0.    1.    1.414 1.   ]
 [1.    0.    1.    1.414]
 [1.414 1.    0.    1.   ]
 [1.    1.414 1.    0.   ]]

[1] 古典ソルバー (ベースライン)
  最適ルート : 東京 → 名古屋 → 大阪 → 京都 → 東京
  目的関数値 : 4.0000

[2] QAOA シミュレーター (reps=2)
  最適ルート : 東京 → 名古屋 → 大阪 → 京都 → 東京
  目的関数値 : 4.0000

古典ソルバーと同じ最適解が得られました。

すいません。実機での実行結果はまだ得られていません。
フリープランのため、実行できる上限に達しており、10月近くにならないと回復しないようです。
とほほ。。

量子回路のイメージ

QAOA の量子回路は、大きく 3 つのブロックで構成されます。

|0⟩ ─── H ─── [コストゲート(γ)] ─── [ミキサーゲート(β)] ─── 測定
|0⟩ ─── H ─── [コストゲート(γ)] ─── [ミキサーゲート(β)] ─── 測定
...
  • H (アダマールゲート): 全状態の重ね合わせを作る。「すべてのルートを同時に考える」状態を準備する
  • コストゲート: 移動距離が長いルートの状態に「重み」をつけてコストを反映する
  • ミキサーゲート: 状態を混ぜ合わせて、より良い解へ誘導する

QAOA の限界と今後の展望

特性 内容
都市数の制限 4都市では 16量子ビット必要。都市数が増えると現状の実機では難しい
ノイズの影響 実機では量子ビットにノイズがあり、測定誤差が生じる
層数 p の選択 p を増やすと精度は上がるが、回路深度が増えてノイズが増える
古典との比較 現状は古典アルゴリズムのほうが高速。「量子優位性」はまだ研究段階

量子コンピュータのハードウェアが進化し、エラー訂正技術が成熟すれば、より大規模な組み合わせ最適化問題で量子優位性が示されると期待されています。

まとめ

  • 巡回セールスマン問題を QUBO 形式に変換し、QAOA で解く実装を紹介しました
  • Qiskit の qiskit-optimization ライブラリを使えば、QUBO変換と QAOA実行が数十行で書けます
  • IBM Quantum の実機は QiskitRuntimeService + Session で簡単に接続できます
  • 現状は小規模問題向けですが、量子コンピュータの進化とともに適用範囲が広がります

コード全文は GitHub で公開しています。ぜひ試してみてください!

最後に

はい、IBM Bobの力をかりて「巡回セールスマン問題」に取り組んでみました。
素因数分解、量子機械学習モデルの実装、そして巡回セールスマン問題を解くところまで、IBM Bobがすべて実装してくれました。

今後は、最適化問題をはじめ、多くの計算量が必要な問題は、量子コンピュータで解いていき、時間を短縮して成果を出していくことになると思います。

Bobの力を借りれば、量子コンピュータを使うハードルが大きく下がると思いますので、色々取り組んで勉強していきたいと思います。

今回は、以上です。

参考文献

紹介

IBM Bob紹介ページ

IBM Quantum Platform

SPSS Modeler ノードリファレンス目次

SPSS Modeler 逆引きストリーム集

SPSS funさん記事集

IBM 斎藤さんの記事集

SPSS連載ブログバックナンバー

SPSSヒモトクブログなどは以下のTechXchangeのコミュニティに統合されました。
ご興味がある方は、ぜひiBM IDを登録して参加してみてください！！！お待ちしています。

IBM TechXchange Data Science Japan

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?