QUBOって何？

執筆日

2025/10/27

私のスペック

量子コンピューターを勉強し始めて、1か月のペーペー。

やること

この記事では、QUBOの基本と、実際の問題をQUBOに変換する方法をペーペーが勉強したことをメモとして残します。

GPT-5に聞いてみる

以下回答..

QUBO（Quadratic Unconstrained Binary Optimization）は、量子コンピューティングや組合せ最適化の分野でよく使われる数学的な定式化です。以下のような特徴があります：
🔹 QUBOの定義

QUBOは、次のような形式の最適化問題です：

$$
\text{minimize } x^T Q x
$$

ここで：

- \( x \) は **バイナリ変数ベクトル**（各要素は 0 または 1）
- \( Q \) は **対称な実数値の行列**（問題の構造を表す）

---
🔹 QUBOの特徴

- **制約なし（Unconstrained）**：制約条件はすべて目的関数に組み込まれている
- **2次形式（Quadratic）**：目的関数は2次の項までしか含まない
- **バイナリ変数（Binary）**：変数は0か1のみを取る
---
🔹 QUBOの応用例
QUBOは以下のような問題に応用されます：

- グラフ彩色問題
- 最大クリーク問題
- ナップサック問題
- スケジューリング
- 機械学習（例：クラスタリング）
- 量子アニーリング（D-Waveなどの量子コンピュータで解く）

---
🔹 QUBOと量子コンピュータ

QUBOは、量子アニーリング型の量子コンピュータ（例：D-Wave）で直接解くことができる形式です。量子アニーリングは、エネルギー最小化問題としてQUBOを解くために設計されています。
---

ワケワカラン(´；ω；`)

まずは語源から..

QUBOとは、Quadratic Unconstrained Binary Optimization（非制約二値変数二次最適化）の頭文字をとったものです。
Quadratic : 二次。数学における「2次式」や「2次関数」を指す
Unconstrained：無制約。最適化問題において制約条件が存在しない
Binary : 変数が 0 または 1 の2つの値しか取らない
Optimization：最適化。ある目的関数（目標）を最大化または最小化するように、変数の値を調整すること。

数式で書くと...

$$\mathbf{x} = (x_1, x_2, \dots, x_M), \quad x_i \in \{0,1\}$$

という M個のバイナリ変数に対して、次の二次形式の評価関数を最小化します：

$$f(\mathbf{x}) = \mathbf{x} Q \mathbf{x}^T = \sum_{i=1}^{M} \sum_{j=1}^{M} Q_{i,j} x_i x_j$$

アタマガイタイ...(´；ω；`)

参考記事

https://zenn.dev/headwaters/articles/86d609807818ec

https://scisimple.com/ja/articles/2025-02-20-liang-zi-konpiyutanotamenoqubonojian-lue-hua--a3je86r

GPT-5に例を出してもらう

実例：ナップサック問題をQUBOで表現

問題設定

• アイテム数：3個
• 価値：( v = [10, 7, 5] )
• 重さ：( w = [3, 2, 1] )
• 容量制限：( W = 4 )

目的：
価値の合計を最大化しつつ、重さの合計が容量 ( W ) を超えないようにする。

---

1. バイナリ変数の定義

各アイテムを選ぶかどうかをバイナリ変数で表す：

$$x_i \in \{0,1\}, \quad i = 1,2,3$$

---

2. 評価関数（目的関数）

価値を最大化 → QUBOでは最小化問題なので、負の価値を使う：

$$\text{maximize } \sum v_i x_i \quad \Leftrightarrow \quad \text{minimize } -\sum v_i x_i$$

---

3. 制約をペナルティ項に変換

重さの合計が ( W ) を超えないように：

$$\sum w_i x_i \leq W$$

これをペナルティ項に：

$$\lambda (\sum w_i x_i - W)^2$$

ここで (\lambda) はペナルティ係数。

---

4. QUBO形式の評価関数

$$f(x) = -\sum_{i=1}^3 v_i x_i + \lambda (\sum_{i=1}^3 w_i x_i - W)^2$$

展開すると：

$$f(x) = -(10x_1 + 7x_2 + 5x_3) + \lambda ((3x_1 + 2x_2 + x_3 - 4)^2)$$

これを展開して、QUBO行列 ( Q ) に変換します。

ワカリヤスイ(・∀・)!!
ちょっとわかってきた

QUBO行列を求める

main.py

import numpy as np

# アイテムの価値と重さ
values = np.array([10, 7, 5])
weights = np.array([3, 2, 1])
W = 4
lambda_penalty = 5

# QUBO行列を作成
Q = np.zeros((3, 3))
for i in range(3):
    Q[i, i] = -values[i] + lambda_penalty * weights[i]**2
    for j in range(i+1, 3):
        Q[i, j] = lambda_penalty * 2 * weights[i] * weights[j]

print("QUBO行列:\n", Q)

QUBO行列:
 [[35. 60. 30.]
 [ 0. 13. 20.]
 [ 0.  0.  0.]]

QUBO行列 とは..

評価関数

$$f(x) = \sum_{i=1}^M \sum_{j=1}^M Q_{i,j} x_i x_j$$

を定義するための行列です。

• 対角成分 ( Q_{ii} )
  → 各変数 ( x_i ) の「単独の重み」
  → ナップサックの場合、価値とペナルティの影響を受けます。

• 非対角成分 ( Q_{ij} )（i≠j）
  → 変数間の「相互作用」
  → ペナルティ項の展開で出てくるクロス項（重さの組み合わせによる影響）

GPT-5スゴイ..なんとなくわかってきた

参考記事

https://vigne-cla.com/21-27/