💡

PyQuboでSAとSQAを試してみた

2025/08/12に公開

注意: この記事はLLM支援で執筆されていますが、実験結果や具体的な数値はすべて実際のコード実行で確認済みです。理論的な説明と実装の詳細は、筆者が実際にPyQuboとOpenJijで検証した内容に基づいています。

 はじめにPyQuboとOpenJijを使って量子アニーリングの世界に足を踏み入れてみました。最初は簡単な問題から始めて、最終的にTSPでSAとSQAの決定的な違いを発見することになります。

 準備運動：整数分割問題とナップサック問題
 整数分割問題まずは最もシンプルな問題から。整数の集合を2つのグループに分けて、合計値を等しくする問題です。
from pyqubo import Spin

# 数値リスト [1, 2, 3, 4] を2グループに分割
s = [Spin(f's_{i}') for i in range(4)]
numbers = [1, 2, 3, 4]

# ハミルトニアン：(グループAの和 - グループBの和)^2
sum_diff = sum(numbers[i] * s[i] for i in range(4))
H = sum_diff ** 2

# PyQuboモデルのコンパイル
model = H.compile()

# QUBO形式への変換
qubo, offset = model.to_qubo()

# シミュレーテッドアニーリングで解く
from openjij import SASampler
sampler = SASampler()
response = sampler.sample_qubo(qubo, num_reads=100)

# 結果の取得
best_sample = response.first.sample
best_energy = response.first.energy

# 元の変数表現に戻す
decoded = model.decode_sample(best_sample, vartype='SPIN')
print(f"解: {decoded.sample}")
print(f"エネルギー: {best_energy}")
Spinを+1/-1で2グループを表現。きれいに解けました！

 ナップサック問題次は制約付き最適化の入門編。
from pyqubo import Binary

# アイテムi を選ぶかどうか
x = [Binary(f'x_{i}') for i in range(n)]

# 目的：価値最大化、制約：重量上限
H = -sum(values[i] * x[i]) + λ * (sum(weights[i] * x[i]) - capacity) ** 2

# PyQuboモデルのコンパイル
model = H.compile()

# QUBO形式への変換
qubo, offset = model.to_qubo()

# シミュレーテッドアニーリングで解く
from openjij import SASampler
sampler = SASampler()
response = sampler.sample_qubo(qubo, num_reads=100)

# 結果の取得と制約チェック
best_sample = response.first.sample
best_energy = response.first.energy

# 元の変数表現に戻す
decoded = model.decode_sample(best_sample, vartype='BINARY')
print(f"選択されたアイテム: {decoded.sample}")
print(f"総価値: {-best_energy}")  # 負の符号を反転

# 制約違反のチェック
broken = decoded.constraints(only_broken=True)
if broken:
    print("制約違反:", broken)
ここで初めて制約係数λが登場。この調整が後で重要になります。

 TSP：順列表現からエッジ表現へ
 順列表現（QUBO行列が巨大に）最初は教科書通りの順列表現で実装しました。
# x[i][t] = 1: 時刻tに都市iを訪問
x = [[Binary(f'x_{i}_{t}') for t in range(n)] for i in range(n)]

# 制約1：各時刻に1都市
# 制約2：各都市を1回訪問
H = H_distance + λ1 * H_one_city_per_time + λ2 * H_one_time_per_city
これで15都市は解けたのですが、問題が...

QUBO変数数 = n² = 225変数！
実機の量子アニーラー（D-Wave）では数千量子ビットあっても、ハードウェアグラフへのマッピングで実質的に扱える問題サイズが制限されます。20都市で400変数、30都市で900変数...現実的ではありません。

 エッジ表現への転換そこでエッジ表現に切り替えました。
# e[(i,j)] = 1: 都市i-j間のエッジを使用
e = {(i,j): Binary(f'e_{i}_{j}') for i in range(n) for j in range(i+1, n)}

# 変数数：n(n-1)/2 （15都市なら105変数）
変数数が大幅削減！でもここから本当の挑戦が始まります。

 部分巡回問題と三角形ペナルティエッジ表現の欠点は部分巡回（小さなループ）ができやすいこと。
都市: A - B - C - A  （3都市の三角形）
     D - E - F - D  （別の三角形）
これを防ぐため、三角形ペナルティを導入：
# 3都市の三角形を抑制
for i, j, k in combinations(range(n), 3):
    H += λ_triangle * (e[i,j] * e[j,k] + e[j,k] * e[i,k] + e[i,j] * e[i,k])
裏の狙い

わざと複雑な制約を課すことでSAよりSQAの方が有利な問題設定を作りたいという意図があります。

 本題：SAとSQAの比較実験
 実験設定同じハミルトニアン、同じ係数でSAとSQAを比較：
# 15都市TSP、各アルゴリズム50回実行
configs = {
    'SA': {'degree_coeff': 10, 'triangle_coeff': 1},
    'SQA': {'degree_coeff': 10, 'triangle_coeff': 1, 'trotter': 16}
}

 衝撃の結果

アルゴリズム
単一ツアー成功率
平均エッジ数
次数制約違反


SA
20%
15個（正解）
0-6

SQA
0%
37-43個
200+

SQAが全く制約を守れない！

 なぜSQAは制約を守れないのか
 原因：Suzuki-Trotter分解SQAは量子効果をシミュレートするために、系をトロッター数L個の層に分解します：
元の系 → L個のレプリカ（トロッタースライス）
このとき、各層での有効的なバリア高さが1/Lに希釈されてしまうのです。
# 理論的な補正
if use_sqa:
    lambda_degree *= trotter  # L倍する必要がある
    lambda_triangle *= trotter

 Optunaで最適係数を探索制約違反最小化を目的関数として、100回の試行で最適化：
def objective(trial):
    degree_mult = trial.suggest_float('degree_mult', 5, 20)
    triangle_mult = trial.suggest_float('triangle_mult', 0.5, 2)

    # SQAの場合はトロッター数をかける
    if use_sqa:
        trotter = trial.suggest_int('trotter', 8, 32, step=8)
        degree_coeff = trotter * degree_mult
        triangle_coeff = trotter * triangle_mult

 最適化結果

アルゴリズム
degree係数
triangle係数
備考


SA
8.83
0.18
-

SQA
370.24
20.8
trotter=32で約40倍

理論予測（32倍）とほぼ一致！





SQAの場合は温度に比例する熱揺らぎに加え、量子揺らぎによって低い温度で複雑なエネルギー面を走査することができるため、高sweep領域でも最小距離が改善してることがわかると思います。　一方で、量子揺らぎのトンネル効果によって成功確率はsweepを増やすとSAに負けると考えられ、期待通りの挙動が得られています。

 実装上の教訓
 1. 問題の定式化は重要
順列表現：理論的にきれいだが変数数が爆発

エッジ表現：コンパクトだが部分巡回対策が必要

 2. SQA使用時の注意点# SAで動いた係数をSQAに適用する際
sqa_coeff = sa_coeff * trotter_number

# さらに微調整が必要な場合も
sqa_coeff *= 1.2  # 実験的な補正

 3. 制約の種類による違い
等式制約（次数=2）：特に違反しやすい

不等式制約（重量≤上限）：比較的守りやすい

ペナルティ項（三角形抑制）：効果が薄れる

 まとめ：量子アニーリングへの道PyQuboで様々な問題を実装し、SAとSQAを比較した結果：

簡単な問題から始める重要性：整数分割→ナップサック→TSPと段階的に

ハードウェアを意識した定式化：変数数とグラフ構造の考慮

SQAの特性理解：制約係数のトロッタースケーリング
実機の量子アニーラーを使う前に、SQAでの検証は必須です。ただし、制約の扱いが根本的に異なることを理解した上で、適切なパラメータ調整を行う必要があります。

 今後の展望D-Wave実機での検証（APIキー取得済み）
より効率的な部分巡回除去手法
動的な係数調整アルゴリズム
量子アニーリングは魅力的ですが、古典手法との違いを理解することが実用化への第一歩です。PyQuboとOpenJijは、その学習に最適なツールでした。
コードはGitHubで公開しています。皆さんも是非、制約最適化でのSA/SQAの違いを体験してみてください！

はじめに

準備運動：整数分割問題とナップサック問題

整数分割問題

ナップサック問題

TSP：順列表現からエッジ表現へ

順列表現（QUBO行列が巨大に）

エッジ表現への転換

部分巡回問題と三角形ペナルティ

本題：SAとSQAの比較実験

実験設定

衝撃の結果

なぜSQAは制約を守れないのか

原因：Suzuki-Trotter分解

Optunaで最適係数を探索

最適化結果

実装上の教訓

1. 問題の定式化は重要

2. SQA使用時の注意点

3. 制約の種類による違い

まとめ：量子アニーリングへの道

今後の展望

Discussion