はじめに
2019年から2022年にかけて量子アニーリングに関する業務を行っていました。
業務に携わる中で、どのようなOSSがあるかを調査したり、量子アニーリングをPythonで扱うにはどうするかを検証してきました。特に業務をやっていた中で、最適化問題を数式で表現するのが一番、苦労したところでした。
本記事では、業務での経験をもとに、量子アニーリングがどういったもので、どのような考え方で、最適化問題を数式表現できるのかの一例を紹介していきます。
量子コンピュータ
量子力学の物理状態・性質を活用した高速計算が可能なコンピュータのことです。
要は、以下のような人間が頭や手で計算することが困難な式の解を高速に導くことができるコンピュータのことです。
$\sum_{α, β}\sum_{i}d_{αβ}q_{αi}q_{β, i+1} + a\sum_{α}(\sum_{i}q_{αi} - 1)^2 + b\sum_{i}(\sum_{α}q_{αi} - 1)^2$
量子コンピュータのアルゴリズムは、ゲート型とアニーリング型の2種類に分類されるが、本記事では、アニーリング型に着目して説明します。
量子アニーリングとは
- 任意の最適化問題で取りうる多数の解の組み合わせから、よりベストな解(最適解)を探索するためのアルゴリズムのことです。
量子アニーリングで最適化問題を解くには？
-
前提として、量子アニーリングを扱うには、数式で表現できる最適化問題である必要があります。
-
量子アニーリングの世界で、最適化問題を数式で表現することを「定式化」と言うこともあります。
-
ナップサック問題を例に説明します。
- 目的: できるだけバッグに詰める品物の値段を最大。
- 制約条件: バッグに詰めれる品物の重さは、3000gまで。
- 定式化に使うスピン($x_{*}$)は、QUBOモデル (1/0のバイナリ表現)。
- スピン値について、品物を詰める(1), 品物を詰めない(0)と定義。
| 品物 | 値段 (円) | 容量 (g) |
|---|---|---|
| 金塊 | 12000 | 2500 |
| 壺 | 2500 | 800 |
| 指輪 | 100 | 30 |
| ネックレス | 200 | 50 |
| 現金 | 3000 | 600 |
| 置物 | 5000 | 1300 |
| 絵画 | 8500 | 1700 |
| 腕時計 | 700 | 250 |
定式化の例
- 目的関数の例
- 品物を詰めるほど、式の結果が最小。
H1 = $-(12000x_{1} + 2500x_{2} + 100x_{3} + 200x_{4} + 3000x_{5} + 5000x_{6} + 8500x_{7} + 700x_{8})$
- 制約条件の例
- 品物の重量合計が3000gの時に、式の結果が最小。
H2 = $(3000 - (2500x_{1} + 800x_{2} + 30x_{3} + 50x_{4} + 600x_{5} + 1300x_{6} + 1700x_{7} + 250x_{8}))^2$
定式化をするにあたり、量子の世界では、エネルギーが収束する時に最適解を得られやすい性質を持つため、期待した最適解の時に、数式の計算結果が最小となるように考える。 というのが一つのコツです。
実際にPythonでナップサック問題を解く
Pythonには量子アニーリングに関するライブラリが豊富にあります。
本記事では、pyquboとdwave-ocean-sdkを使った例を紹介します。
-
pyqubo
- (株) リクルートコミュニケーションズが開発しているOSS。
- 最適化問題の定式化表現機能を搭載したツールセット。
- D-Wave社などが提供しているアニーリングマシンに投入できるQUBOデータを作成。
-
dwave-ocean-sdk
- カナダのD-Wave社が提供しているOSS。
- 無償で量子アニーリングのシミュレーションができるIFを提供。
- D-Wave社は、実機の量子コンピュータの開発なども行っており、実機に接続するためのIFも本SDKに包含。
- 実機を使う場合は、有償のトークンが必要となるので注意が必要。
ライブラリのインストール
- python3系をインストール済みの環境でpipコマンドを実行します。
$ pip install pyqubo
$ pip install dwave-ocean-sdk
サンプルコード例
- pyquboで作成したquboモデルをdwave-ocean-sdkで実際に量子アニーリングを実行します。
import neal
from pyqubo import Array, Constraint
N = 8
limit_weight = 3000
num_reads = 10
def check(result):
for r in result.data(['sample']):
spin = r.sample
if spin["x[5]"] == 1 and spin["x[6]"] == 1:
print(spin)
return True
return False
def create_model():
x = Array.create('x', shape=N, vartype='BINARY')
H1 = - (12000*x[0] + 2500*x[1] + 100*x[2] + 200*x[3] + 3000*x[4] + 5000*x[5] + 8500*x[6] + 700*x[7])
H2 = Constraint((limit_weight - (2500*x[0] + 800*x[1] + 30*x[2] + 50*x[3] + 600*x[4] + 1300*x[5] + 1700*x[6] + 250*x[7]))**2, "const")
H = H1 + H2
model = H.compile()
qubo, offset = model.to_qubo(feed_dict={"const": 1.0})
return qubo, offset
def exe(qubo):
sampler = neal.SimulatedAnnealingSampler()
result = sampler.sample_qubo(qubo, num_reads=num_reads)
return result
if __name__ == "__main__":
qubo, offset = create_model()
result = exe(qubo)
if check(result):
print("Success")
else:
print("Failed")
実行結果例
最適解である値段合計=13500円, 容量合計=3000g の解を量子アニーリングで
探索できます。 (置物(x[5]), 絵画(x[6]))
※ 確率上、最適解を取得できないケースもあるので、その場合は、num_reads値を増やすことを推奨します。
{'x[0]': 0, 'x[1]': 0, 'x[2]': 0, 'x[3]': 0, 'x[4]': 0, 'x[5]': 1, 'x[6]': 1, 'x[7]': 0}
Success
| スピン名 | 品物 | 値段 (円) | 容量 (g) | スピン値(1/0) |
|---|---|---|---|---|
| x[0] | 金塊 | 12000 | 2500 | 0 |
| x[1] | 壺 | 2500 | 800 | 0 |
| x[2] | 指輪 | 100 | 30 | 0 |
| x[3] | ネックレス | 200 | 50 | 0 |
| x[4] | 現金 | 3000 | 600 | 0 |
| x[5] | 置物 | 5000 | 1300 | 1 |
| x[6] | 絵画 | 8500 | 1700 | 1 |
| x[7] | 腕時計 | 700 | 250 | 0 |
まとめ
今後は、より効率よく最適解を求める方法や、D-Wave社以外のアニーリングマシンを使った例も紹介していく予定です。