1. QUBOとは？
定義
QUBO（Quadratic Unconstrained Binary Optimization）は以下のような最適化問題：
minimize: xᵀ Q x
-
x: 0または1からなるバイナリ変数ベクトル（各要素は 0 または 1）（例：x = [0,1,1,0,...]） -
Q: 係数が入った正方行列（n×n）
目的：
Qの中の係数に従って、xの組み合わせ（すべて0と1）で最小値となるものを探すこと。
- QAOAとは？（Quantum Approximate Optimization Algorithm）
QAOAは、量子コンピュータ上で組合せ最適化問題を近似的に解くアルゴリズム。
ハーバード大学のFarhiや、Gutmann等によって提案された。
概要：
QAOAは次のように動きます：
QUBOやMaxCutなどをIsingモデルに変換
Hamiltonian（H_C）とミキサーHamiltonian（H_M）を用意
両者を交互にパラメータ付きで適用して量子状態を作る
パラメータ（γ, β）を古典コンピュータで最適化
最終状態を測定して、最も良い解（x）を得る
QUBOとQAOAの関係
QUBOはQAOAに与える入力形式の一つです。
QAOAで使うには、以下のようなステップが必要：
変換の流れ
組合せ最適化問題
↓
QUBO形式にする（またはIsingモデルに変換）
↓
QUBO → Isingモデル（スピン形式）
↓
QAOAで解く
QUBOとIsingモデルの変換
QUBOは0-1変数を使うが、Isingモデルは±1（スピン）を使用：
QUBO変数 x ∈ {0,1} を Ising変数 s ∈ {-1, +1} に変換
x = (1 + s) / 2
この変換によって、QUBOを量子コンピュータが扱える形式（Hamiltonian）に変換できる。
具体例：MaxCut問題
問題：グラフのノードを2つのグループに分け、切られるエッジの数を最大化する。
QUBO形式に変換：
ノードiとjが同じグループにあるとき：
x_i = x_j → エッジが切られない → 0
x_i ≠ x_j → エッジが切られる → 1
目的関数：
maximize ∑_{i,j ∈ E} x_i(1 - x_j) + x_j(1 - x_i)
→ QUBO形式に落とし込める
このQUBOをQAOAに入力し、最適なノード分割（カット）を量子コンピュータで求める。
| 用語 | 意味 |
|---|---|
| QUBO | 0-1のバイナリ変数で記述された最適化問題。Q行列に従い目的関数を最小化。 |
| Isingモデル | ±1のスピン変数を用いた物理モデル。QUBOと等価な形式に変換可能。 |
| QAOA | Ising形式の最適化問題を量子回路で近似的に解くアルゴリズム。QUBO→Isingを経て使用。 |
[組合せ問題]
↓ QUBO化
[QUBO: xᵀ Q x] → [Isingモデル: H_C]
↓
[QAOA（量子回路）]
↓
[最適または準最適解]
QUBO → Ising変換とQAOA回路設計
2. QUBO → Ising変換
量子アルゴリズム（特にQAOA）は スピン変数 s ∈ {-1, +1} を使うため、QUBOをIsingモデルに変換する必要がある。
変換式
x ∈ {0,1} → s ∈ {-1, +1}
x = (1 + s) / 2
✅ 変換用Pythonコード（QUBO→Ising）
import numpy as np
def qubo_to_ising(Q):
n = Q.shape[0]
h = np.zeros(n)
J = np.zeros((n, n))
offset = 0
for i in range(n):
for j in range(n):
q = Q[i, j]
if i == j:
offset += q / 4
h[i] += q / 4
else:
offset += q / 4
h[i] += q / 4
h[j] += q / 4
J[i, j] += q / 4
return h, J, offset
例：QUBO定義と変換
Q = np.array([
[2, -2],
[-2, 1]
])
h, J, offset = qubo_to_ising(Q)
print("h =", h)
print("J =", J)
print("offset =", offset)
- QAOA（量子近似最適化アルゴリズム）
QAOAは、Isingモデルの最小値を量子回路で近似的に求めるアルゴリズム。
QAOAの基本ステップ（深さ p=1）
初期状態 |+⟩ を用意（各量子ビットにHゲート）
コスト演算（Z演算子をベースにした位相回転）
ミキサー演算（X演算子をベースにした回転）
測定
パラメータ β, γ を最適化
QAOA量子回路のPythonコード（Qiskit）
from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
# パラメータ定義
beta = Parameter('β')
gamma = Parameter('γ')
# Isingパラメータ（例）
h = [0.25, 0.25]
J = {(0, 1): -0.5}
# QAOA回路作成
qc = QuantumCircuit(2)
qc.h([0, 1]) # 初期状態
# コストユニタリ（Z演算）
qc.rz(2 * gamma * h[0], 0)
qc.rz(2 * gamma * h[1], 1)
qc.cx(0, 1)
qc.rz(2 * gamma * J[(0, 1)], 1)
qc.cx(0, 1)
# ミキサーユニタリ（X演算）
qc.rx(2 * beta, 0)
qc.rx(2 * beta, 1)
qc.draw('mpl')
- 結果の評価（エネルギー期待値の計算）
from qiskit import Aer
from qiskit.opflow import Z, I, StateFn, CircuitStateFn
# Hamiltonian定義（Z演算子で構築）
H = h[0]*Z^I + h[1]*I^Z + J[(0,1)]*Z^Z
# パラメータを固定
param_values = {gamma: np.pi/4, beta: np.pi/8}
bound_qc = qc.bind_parameters(param_values)
# 状態とエネルギー評価
backend = Aer.get_backend('aer_simulator_statevector')
state = CircuitStateFn(bound_qc)
energy = (~state @ H @ state).eval().real
print("エネルギー期待値 =", energy)
まとめ
| 項目 | 説明 |
|---|---|
| QUBO | 0-1変数の2次最適化問題 |
| Isingモデル | ±1変数によるスピン物理モデル |
| QAOA | Ising形式の目的関数を量子回路で最適化 |
| 変換 |
x = (1 + s) / 2 を用いてQUBO→Ising変換 |
| 回路構成 | 初期状態 + コスト演算 + ミキサー演算 |
参考
Qiskit Optimization
Farhi et al. (QAOA original paper)
D-Wave QUBO/Ising変換解説
Discussion