量子コンピューターを用いた最適化アルゴリズムの一つに、Quantum Approximation Optimization Algorithm (QAOA) があります。このアルゴリズムは主にゲート型の量子コンピューターで動作するアルゴリズムであり、実行するには量子回路のシミュレーターもしくは本物の量子コンピューターが必要です。
本記事ではIBMが開発している本物の量子コンピューターを用いて組合せ最適化問題を解いてみます。特にQuadratic Binary Unconstrained Optimization (QUBO)と呼ばれる問題を対象とします。
準備
計算機環境
アーキテクチャ: x86_64
CPU: Intel(R) Xeon(R) Silver 4216 CPU @ 2.10GHz x 2 (16 x 2=32 cores)
RAM: 754GiB
OS: Ubuntu 24.04 LTS使用するライブラリ・Pythonのバージョン
Python 3.11.9
---
docplex==2.27.239
numpy==1.25.2
qiskit==1.1.0
qiskit-algorithms==0.3.0
qiskit-ibm-runtime==0.26.0
qiskit-optimization==0.6.1実装
なるべく自分で量子回路を実装することは避け、既存のプログラムを再利用する方針で実装します。
問題の作成
今回はQUBOと呼ばれる問題を対象として実験を行います。QUBOの目的関数は、$Q$を係数行列、$x$を0か1の二値を成分とするベクトル変数として、$x^\top Qx$のように表現されます。今回はQ行列の要素を-1から1の範囲で一様ランダムに生成しすることで問題を作成します。
Qiskitを用いてQUBOを解く
QiskitはPythonでゲート型の量子コンピュータ（およびそのシミュレーター）を扱うためのライブラリです。qiskit-communityには具体的な量子回路の実装に用いるqiskitだけでなく、関連するアルゴリズムや有名な量子回路がすでに実装されたライブラリも用意されています。今回はqiskit-algorithmsに実装されているQAOAを用いて最適化を行います。
BackendとしてIBMQを選択する
SamplerとBackendを変更することで、量子回路での計算を実行するデバイスを変更できます。例えばcuQuantumなどのGPUシミュレーターを使用したい場合、IBMQなどの実機を使用したい場合には、SamplerとBackendを適切に変更する必要があります。IBMQを使用する場合の具体的な実装は以下に記述します。
from qiskit_algorithms import QAOA
from qiskit_algorithms.optimizers import SPSA
from qiskit_ibm_runtime import QiskitRuntimeService, Session, Sampler
# from qiskit_ibm_runtime import SamplerV2 as Sampler
service = QiskitRuntimeService(channel="ibm_quantum", token="Type your token")
backend = service.least_busy(operational=True, simulator=False)
spsa = SPSA(maxiter=250)
with Session(backend=backend) as session:
sampler = Sampler(mode=session)
qaoa = QAOA(sampler=sampler, optimizer=spsa, reps=5)量子回路のtranspileについて
Backendに応じて量子回路を最適化することを、transpileと呼びます。BackendとしてIBMQを使う場合にはこのtranspileが必須です。qiskit-algorithmsに実装されているQAOAアルゴリズムは、私が確認した限りでは予め量子回路をtranspileすることが難しそうな様子でした。そこで、以下に述べるように関連するプログラムを書き換えることでIBMQを使えるようにしていきます。
SamplerV1を用いる場合
qiskit_ibm_runtime/sampler.pyを編集します。- SamplerV1はQAOAアルゴリズムの実装と互換性があるインターフェースですが、2024年8月15日にサポートが切れるそうです。
- 次のセクションで説明する、SamplerV2を用いた方法を使いましょう。
def _run( # pylint: disable=arguments-differ
self,
circuits: Sequence[QuantumCircuit],
parameter_values: Sequence[Sequence[float]],
**kwargs: Any,
) -> RuntimeJob:
"""Submit a request to the sampler primitive.
Args:
circuits: A (parameterized) :class:`~qiskit.circuit.QuantumCircuit` or
a list of (parameterized) :class:`~qiskit.circuit.QuantumCircuit`.
parameter_values: An optional list of concrete parameters to be bound.
**kwargs: Individual options to overwrite the default primitive options.
Returns:
Submitted job.
"""
import qiskit
_circuits = [qiskit.compiler.transpile(c, backend=self._backend) for c in circuits]
inputs = {
"circuits": _circuits,
"parameters": [circ.parameters for circ in _circuits],
"parameter_values": parameter_values,
}
return self._run_primitive(
primitive_inputs=inputs, user_kwargs=kwargs.get("_user_kwargs", {})
)SamplerV2を用いる場合
以下の2点に対処することが必要です。
- SamplerV2の仕様に合わせてアルゴリズムを書き換える: https://docs.quantum.ibm.com/migration-guides/v2-primitives
- samplerをrunする前に回路をトランスパイルする
具体的には、以下のようにqiskit_algorithms/minimum_eigensolvers/diagonal_estimator.pyにあるDiagonalEstimatorクラスを修正します。
def _call(
self,
circuits: Sequence[int],
observables: Sequence[int],
parameter_values: Sequence[Sequence[float]],
**run_options,
) -> _DiagonalEstimatorResult:
import qiskit
job = self.sampler.run(
[(qiskit.compiler.transpile(self._circuits[0], backend=self.sampler._backend),
parameter_values)],
**run_options,
)
sampler_result = job.result()
samples = sampler_result[0].data.meas.get_counts()
evaluations: list[dict[int, tuple[float, float]]] = [
{
eval("0b"+state): (probability, _evaluate_sparsepauli(eval("0b"+state), self._observables[0]))
for state, probability in samples.items()
}
]プログラム全体
import numpy as np
from qiskit_ibm_runtime import QiskitRuntimeService, Session, Sampler
# from qiskit_ibm_runtime import SamplerV2 as Sampler
from qiskit_algorithms import QAOA
from qiskit_algorithms.optimizers import SPSA
from docplex.mp.model import Model
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit_optimization.translators import from_docplex_mp
spsa = SPSA(maxiter=250)
service = QiskitRuntimeService(channel="ibm_quantum", token="Type your token")
backend = service.least_busy(operational=True, simulator=False)
num_nodes = 10
Q = 2 * np.random.rand(num_nodes, num_nodes) - 1
with Session(backend=backend) as session:
sampler = Sampler(mode=session)
qaoa = QAOA(sampler=sampler, optimizer=spsa, reps=5)
algorithm = MinimumEigenOptimizer(qaoa)
model = Model()
# Create n binary variables
x = model.binary_var_list(num_nodes)
# Define the objective function to be maximized
model.maximize(
-model.sum(
Q[i, j] * x[i] * x[j] for i in range(num_nodes) for j in range(num_nodes)
)
)
problem = from_docplex_mp(model)
result = algorithm.solve(problem)結果
Queueの番号が一向に減らず、まだ実行されていません…無事実行されたら、もしかしたら最適解との差分を比較するかもしれません。
解の取り出し部分も仕様が異なるようで、修正が必要です。具体的には、qiskit/primitives/base/base_result.pyの_BasePrimitiveResultクラスにある以下の関数の想定入力と、ibm-runtimeが返却するresultの使用が一致していません。ひとまずコメントアウトで凌ぐことにします。
def __post_init__(self) -> None:
"""
Verify that all fields in any inheriting result dataclass are consistent, after
instantiation, with the number of experiments being represented.
This magic method is specific of `dataclasses.dataclass`, therefore all inheriting
classes must have this decorator.
Raises:
TypeError: If one of the data fields is not a Sequence or ``numpy.ndarray``.
ValueError: Inconsistent number of experiments across data fields.
"""
num_experiments = None
for value in self._field_values: # type: Sequence
if num_experiments is None:
num_experiments = len(value)
# TODO: enforce all data fields to be tuples instead of sequences
if not isinstance(value, (Sequence, ndarray)) or isinstance(value, (str, bytes)):
raise TypeError(
f"Expected sequence or `numpy.ndarray`, provided {type(value)} instead."
)
if len(value) != num_experiments:
raise ValueError("Inconsistent number of experiments across data fields.")
10変数のランダム生成したQUBOを解いてみました。QPUを用いて得られた解とGurobiによる最適解との比較は以下のようになります。
Gurobi: -6.9103 (MIP-GAP=0%)
QPU: -6.0803
この記事は役に立ちましたか？
もし参考になりましたら、下記のボタンで教えてください。
コメント