コスト関数を確認しながら基本的なQUBOアプリをつくる


はじめに

これから量子アニーリングやその他のアニーリングアプリを作りたいという人も増えていますので、簡単に手順を確認します。数式なども出ますので、多少の敷居はありますがみていきたいと思います。


概要

概要は、

1、コスト関数となるQUBOを作る

2、上三角行列の形にして計算実行

3、出た答えを取り出してコストを確認

4、必要なら上記ステップを繰り返し

コスト関数を作って、それを実行します。

使えるのは二次式までです。

手順はQUBOを作ってそれを計算実行する

QUBOという数式・上三角行列を作ります。

例題として、

https://github.com/Wildqat/Wildqat/blob/master/examples_ja/tutorial002_one_plus_one_ja.ipynb

1+1をQUBOで実現します。

まず、コスト関数は上記チュートリアル通り、

E = (x-2)^2 = (q_0+2q_1-2)^2 = q_0^2+4q_0q_1-4q_0+4q_1^2-8q_1+4\\ 

=-3q_0+4q_0q_1-4q_1 +4

こうなりました。定数項以外のところを行列にいれます。

wildqatを準備して、

import wildqat as wq

import numpy as np
a = wq.opt()

a.qubo = [[-3,4],[0,-4]]

a.sa()

#=>[0, 1]

これは、答えを満たしています。

x = q_0+2q_1

とおきましたので、

0+2*1=2となります。


コストを確認する

今回問題が正しいかどうかはコストを見ることで判断できます。

最初のQUBOの式はこの場合最小値は=0の時になりますので、

上記のEの式が0となれば正しい答えであることがわかります。

また、定数項4はQUBOmatrixには入らないので、上記のQUBOmatrixに対応するエネルギーは-4となればOKです。

wildqatから、保存されたエネルギーのリストの最後の要素を抜き出して見ると、

print(a.E[-1])

# => -4.0

コストが-4となっているので、これが答えであることが確認できます。

matplotlibでコスト推移を確認する

念のため、コストの推移を確認してみます。

a.plot()

得られたのは、

2.png

-3.0と-4.0をウロウロしながら、最終的に-4.0に収束しています。

問題が単純だったので、コスト推移も単調ですが、きちんと収束したこと確認ができました。

こちらはシミュレータなので途中経過が確認できますが、実際のアニーリングマシンなどは途中経過の把握は多少困難なので、最終のコストで確認するのが良いかと思います。


自然数分割問題で見て見る

[3,2,6,9,2,5,7,3,3,6,7,3,5,3,2,2,2,6,8,4,6,3,3,6,4,3,3,2,2,5,8,9]という自然数を2つのグループに分けてそれぞれのグループ内の自然数の和が同じになるような分類問題をQUBOで一般化した上で行って見たいと思います。

例題は、こちらにあります。

https://github.com/Wildqat/Wildqat/blob/master/examples_ja/tutorial003_numberpartitioning_ja.ipynb

正直素晴らしいですね。引用します。

4.png

ということで、早速解いて見ますと、

numbers = np.array([3,2,6,9,2,5,7,3,3,6,7,3,5,3,2,2,2,6,8,4,6,3,3,6,4,3,3,2,2,5,8,9])

a.qubo = np.zeros((numbers.size,numbers.size))
for i in range(numbers.size):
for j in range(numbers.size):
if i == j:
a.qubo[i][i]=numbers[i]**2-numbers.sum()*numbers[i]
elif i<j:
a.qubo[i][j]=2*numbers[i] * numbers[j]
answer = a.sa()

この時点で実行されて結果がanswerの中に入ります。答えは量子ビットの0と1の配列で返されてこれだけでは訳がわからないので、しっかり整理してもらいました。

group1_string = ""

group2_string = ""
group1_sum = 0
group2_sum = 0
for i in range(numbers.size):
if answer[i] == 0:
group1_string+= '+' + str(numbers[i])
group1_sum+=numbers[i]
else:
group2_string+= '+' + str(numbers[i])
group2_sum+=numbers[i]

print(group1_string[1:],"=",group1_sum)
print(group2_string[1:],"=",group2_sum)

こちらを実行するときちんと両方とも71になっているのが確認できました。

3+2+9+7+3+3+2+2+8+4+6+3+3+2+5+9 = 71

6+2+5+3+6+7+3+5+2+6+3+6+4+3+2+8 = 71


コストを確認する

これだけの計算ならコスト推移も面白そうです。

a.plot()

こうなりました。

5.png

ちなみに最終のコストは、

print(a.E[0]) #最初のエネルギー

-4977.0

print(a.E[-1]) #listに-1いれると後ろから数える。
-5041.0


もいっちょ例題

変化が見たいので、2000量子ビットから1500選ぶでやってみます。

import wildqat as wq

a = wq.opt()
a.qubo = wq.sel(2000,1500) #2000から1500選ぶ
a.sa()

結果は77秒かかりましたが大きな配列が出ました。肝心のグラフは、、、

a.plot()

6.png

アルゴリズムが優秀すぎてあまり面白い結果にはなりませんでしたが、できました。


繰り返し計算

繰り返し計算し、コストのヒストグラムを求めることで答えを確認することができます。

import matplotlib.pyplot as plt

a.qubo = wq.sel(20,1)
Earr = []
for i in range(100):
a.sa()
Earr.append(a.E[-1])

plt.hist(Earr)
plt.show()

7.png

結果は、100回やって同じ答えでしたので、これが正解で良さそうです。


まとめ

このようにコストを確認することでより良い答えを探したり、問題によってはコストが0になるので、答えが正しいかどうかを確認できます。コストにばらつきがある場合には繰り返し同じ問題を計算して頻度やコストを見ることで正解に近いものを判断することもできます。