はじめに
量子コンピューティングの応用例として、組合せ最適化問題を解くアプローチが注目されています。本記事では、VQE（Variational Quantum Eigensolver） を用いて 数分割問題（Number Partitioning Problem, NPP） を解く実装例を紹介します。
VQEは、古典コンピュータと量子コンピュータのハイブリッドアルゴリズムであり、NISQ（Noisy Intermediate-Scale Quantum）デバイスでも実行可能な点が特徴です。
VQE（変分量子固有値ソルバー）とは
変分法の基礎
VQEを理解するには、まず変分法の原理を知る必要があります。
変分法は、量子力学において基底状態（最小エネルギー状態）を近似的に求める手法です。その核心は変分原理にあります：
$$
E_0 \leq \langle \psi | H | \psi \rangle
$$
ここで：
- $E_0$: ハミルトニアン $H$ の最小固有値（基底状態エネルギー）
- $|\psi\rangle$: 任意の正規化された量子状態
- $\langle \psi | H | \psi \rangle$: 状態 $|\psi\rangle$ におけるエネルギーの期待値
変分原理が言っていること
「どんな量子状態を選んでも、そのエネルギー期待値は必ず真の基底状態エネルギー以上になる」
つまり、様々な状態 $|\psi\rangle$ を試して、期待値 $\langle \psi | H | \psi \rangle$ を最小化すれば、基底状態 $E_0$ に近づけます！
パラメータ化された量子状態
変分法では、パラメータ $\theta$ を持つ量子状態 $|\psi(\theta)\rangle$ を用意します：
$$
|\psi(\theta)\rangle = U(\theta) |0\rangle
$$
- $U(\theta)$: パラメータ化されたユニタリ演算子（量子回路）
- $|0\rangle$: 初期状態（すべての量子ビットが $|0\rangle$）
- $\theta = (\theta_1, \theta_2, \ldots, \theta_n)$: 調整可能なパラメータ
エネルギー関数
パラメータ $\theta$ の関数として、期待値を定義します：
$$
E(\theta) = \langle \psi(\theta) | H | \psi(\theta) \rangle
$$
この $E(\theta)$ を最小化する $\theta^*$ を見つければ、基底状態に最も近い状態が得られます
VQEのアルゴリズム
VQEは、変分法を量子コンピュータで実装したハイブリッドアルゴリズムです。
ステップ詳細
-
初期化（古典）
- パラメータ $\theta$ をランダムに初期化
-
状態準備（量子）
- パラメータ化量子回路 $U(\theta)$ を実行
- 状態 $|\psi(\theta)\rangle$ を生成
-
期待値測定（量子）
- ハミルトニアン $H$ の期待値 $E(\theta)$ を測定
- 複数回の測定で統計的に推定
-
パラメータ最適化（古典）
- 勾配降下法（ADAMなど）で $E(\theta)$ を最小化
- $\theta \leftarrow \theta - \alpha \nabla_\theta E(\theta)$
-
収束判定（古典）
- エネルギー変化が閾値以下なら終了
- そうでなければステップ2に戻る
VQEの特徴と利点
| 項目 | 説明 |
|---|---|
| ハイブリッド | 量子と古典を組み合わせて最適な役割分担 |
| 浅い回路 | NISQ デバイスで実行可能な浅い量子回路 |
| ノイズ耐性 | 誤り訂正なしでもある程度動作 |
| 柔軟性 | 様々な問題に適用可能（化学、最適化など） |
なぜVQEが重要か？
従来の量子アルゴリズム（量子位相推定など）は：
- 深い量子回路が必要
- 誤り訂正が必須
- 現在の量子コンピュータでは実行困難
一方、VQEは：
- 浅い回路で動作
- ノイズに比較的強い
- 今すぐ使える量子アルゴリズム
VQEの応用分野
-
量子化学
- 分子の基底状態エネルギー計算
- 反応経路の探索
-
材料科学
- 新素材の電子状態シミュレーション
-
組合せ最適化（本記事のテーマ！）
- 巡回セールスマン問題
- ポートフォリオ最適化
- 数分割問題（NPP）
-
機械学習
- 量子カーネル法
- 変分量子分類器
数分割問題（NPP）とは
数分割問題（Number Partitioning Problem, NPP）は、与えられた整数の集合を2つのグループに分割し、それぞれの合計値の差ができるだけ小さくなるように分ける問題です。
問題の定義
入力: 整数の集合 (A = {a_1, a_2, \ldots, a_n})
目標:
$$
\min \left| \sum_{i \in S_1} a_i - \sum_{i \in S_2} a_i \right|
$$
これはNPPの標準的な定義です。ただし、量子アルゴリズムでは絶対値を扱いにくいため、同値な次の2乗形式に書き換えて扱います。
$$
\left|A-B\right| \text{を最小}
\quad\Longleftrightarrow\quad
(A-B)^2 \text{を最小}
$$
NPPをイジングモデルとして定式化する
量子アルゴリズムで扱いやすくするために、NPPを直接 Ising モデル（スピン系） に変換します。
スピン変数の導入
各要素 (a_i) に対してスピン変数 (s_i) を定義します：
$$
s_i \in {-1, +1}
$$
- (s_i = +1): 要素 (a_i) はグループ (S_1)
- (s_i = -1): 要素 (a_i) はグループ (S_2)
このときグループ差は次のように書けます：
$$
\sum_{i \in S_1} a_i - \sum_{i \in S_2} a_i
= \sum_i a_i s_i
$$
よって NPP は
$$
H = \left( \sum_i a_i s_i \right)^2
$$
を最小化する問題になります。
イジングハミルトニアンへの展開
$$
\left( \sum_i a_i s_i \right)^2
= \sum_i a_i^2 + 2 \sum_{i<j} a_i a_j s_i s_j
$$
最適化には影響しない定数項（(\sum_i a_i^2)）を落とすと：
$$
H_{\text{Ising}}
= 2\sum_{i<j} a_i a_j ; s_i s_j
$$
これが NPP のイジングモデルです。
量子ビットへのマッピング（Ising → Pauli-Z）
イジング変数 (s_i \in {-1, +1}) は、パウリZ演算子の固有値と一致します：
$$
Z_i |0\rangle = +1|0\rangle,\quad
Z_i |1\rangle = -1|1\rangle
$$
したがって、イジングハミルトニアンはそのまま Pauli-Z の演算子に置き換えられます：
$$
H = \sum_{i<j} 2 a_i a_j , Z_i Z_j
$$
Qiskit では、この (Z_i Z_j) の和を SparsePauliOp として実装します。
このハミルトニアンの最小固有値を VQE で求めることで、NPP の最適解が得られます。
実装コード
以下は、Qiskitを使用したVQEによるNPP求解の実装例です。
import numpy as np
from itertools import combinations
import matplotlib.pyplot as plt
from qiskit.quantum_info import SparsePauliOp
from qiskit.circuit.library import real_amplitudes
from qiskit_aer.primitives import EstimatorV2 as AerEstimator
from qiskit_algorithms.minimum_eigensolvers import VQE
from qiskit_algorithms.optimizers import ADAM
from qiskit.quantum_info import Statevector
from qiskit_algorithms.utils import algorithm_globals
algorithm_globals.random_seed = 100
# 問題設定
a = [2, 3, 4, 5]
n = len(a)
num_qubits = n
# Hamiltonian構築
pauli_list = []
const = sum([x**2 for x in a])
for i, j in combinations(range(n), 2):
coeff = 2 * a[i] * a[j]
z_str = ['I'] * num_qubits
z_str[i] = 'Z'
z_str[j] = 'Z'
pauli_list.append((''.join(reversed(z_str)), coeff))
H = SparsePauliOp.from_list(pauli_list)
# スケーリング（数値安定性のため）
scale = max(1.0, np.max(np.abs(H.coeffs)))
H = SparsePauliOp(H.paulis, H.coeffs / scale)
const /= scale
# Ansatz と Optimizer
ansatz = real_amplitudes(num_qubits, reps=2)
optimizer = ADAM(maxiter=500)
# VQE実行
estimator = AerEstimator()
vqe = VQE(
estimator=estimator,
ansatz=ansatz,
optimizer=optimizer
)
result = vqe.compute_minimum_eigenvalue(operator=H)
まとめ
VQEは、変分法を量子コンピュータで実装した強力な手法であり、NISQ時代の量子コンピュータで現実的に実行可能な組合せ最適化手法として、産業応用が期待されています。この記事が皆さんの量子アルゴリズム学習の助けになれば幸いです。