はじめに

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を使った例を紹介します。

ライブラリのインストール

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社以外のアニーリングマシンを使った例も紹介していく予定です。

参考