@yuichirominato 2018.09.11更新 34views

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

QUBO イジング 量子アニーリング

はじめに

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

概要

概要は、

1、コスト関数となるQUBOを作る
2、上三角行列の形にして計算実行
3、出た答えを取り出してコストを確認
4、必要なら上記ステップを繰り返し

コスト関数を作って、それを実行します。
使えるのは二次式までです。

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

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

例題として、
https://github.com/mdrft/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()

得られたのは、


-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/mdrft/Wildqat/blob/master/examples_ja/tutorial003_numberpartitioning_ja.ipynb

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

引用:https://github.com/mdrft/Wildqat/blob/master/examples_ja/tutorial3_numberpartitioning_ja.ipynb

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


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()

こうなりました。

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


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

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

もいっちょ例題

以前行った下記もやって見たいと思います。

「量子イジング+QUBOでN量子ビットからK量子ビットを選ぶ。」
http://blog.mdrft.com/post/114

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


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

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


a.plot()

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

繰り返し計算

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


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()

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

まとめ

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

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップに戻る

Recent Posts