@yuichirominato 2018.09.09更新

イジング+QUBOでN量子ビットからK量子ビットを選ぶ

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

はじめに

量子ゲートでのQAOAや量子アニーリングなどをやっていると「コスト関数」と「制約条件」と呼ばれる項がでてきます。そのうちの制約条件はよく使われますが、その作り方とルールを確認したいと思います。

N量子ビットからK量子ビット選ぶ

どういうことかというと、{0,1}のバイナリで表現されるN量子ビットがあり、その中からK量子ビットだけを+1、その他を0となるようにイジングモデルをプログラミングしたいとします。実際にはイジングは意識せず、QUBOとよばれるバイナリ値のコスト関数だけを意識してつくることができます。

コスト関数

コスト関数と呼ばれる関数を基本とします。N量子ビットからK量子ビット選ぶコスト関数は、バイナリをとる$q_i$を用いて、下記のようにかけます。

$
E = (\sum_{i=0}^{N}q_i – K)^2
$

QUBOmatrix

QUBOmatrixというものを作れば、それを入力することで問題が解けます。ここで例題を5量子ビットから2量子ビット選ぶという問題でやってみましょう。

・5量子ビットから2量子ビット選ぶ

$
E = (\sum_{i=0}^4 q_i -2)^2 = (\sum_{i=0}^4 q_i)^2 -2*2*(\sum_{i=0}^4 q_i) + 2^2
\\ = (q_0+q_1+q_2+q_3+q_4)^2 -4*(q_0+q_1+q_2+q_3+q_4) + 4
\\ = -3q_0-3q_1-3q_2-3q_3-3q_4+2q_0q_1+2q_0q_2+ \cdots + 2q_3q_4 + 4
$

上記は全てを展開して、バイナリのルール$q_i^2 = q_i$を適用しています。QUBOmatrixに直して、

$
\begin{array}
-&q_0&q_1&q_2&q_3&q_4\\
q_0& -3&2&2&2&2\\
q_1& & -3&2&2&2\\
q_2& & & -3&2&2\\
q_3& & & &-3&2\\
q_4& &&& &-3
\end{array}
$

こうなりましたので、これをSDKに代入します。SDKはwildqatを使用し、インストールは

pip3 install wildqat

です。

from wildqat import opt
a = opt()
a.qubo = [[-3,2,2,2,2],[0,-3,2,2,2],[0,0,-3,2,2],[0,0,0,-3,2],[0,0,0,0,-3]]
a.sa()

これで入力と実行は終わりで、出力は、

1.5225954055786133 #実行時間(s)
[1, 0, 1, 0, 0]

確かにバイナリ値で5量子ビットの中の2量子ビットだけ選ばれています。

一般化

上記行列には明らかにルールがあります。他の例で3量子ビットから1量子ビット選ぶには、

$
E = (\sum_{i=0}^2 q_i -1)^2 = (\sum_{i=0}^2 q_i)^2 -2*1*(\sum_{i=0}^2 q_i) + 1^2
\\ = (q_0+q_1+q_2)^2-2*(q_0+q_1+q_2)+1
\\ = -q_0-q_1-q_2+2q_0q_1+2q_0q_2+2q_1q_2+1
$

QUBOmatrixは、

$
\begin{array}
-&q_0&q_1&q_2\\
q_0& -1&2&2\\
q_1& & -1&2\\
q_2& & & -1
\end{array}
$

対角項が1-2Kで、非対角項が2になります。

from wildqat import opt
a = opt()
a.qubo = [[-1,2,2],[0,-1,2],[0,0,-1]]
a.sa()
1.5346968173980713 #実行時間(s)
[1, 0, 0]

つまり一般化して実行してみると、

N = 5
K = 2
a.qubo = np.diag([1-2*K]*N)+np.triu([[2] * N for i in range(N)],k=1)
a.sa()
1.5199542045593262 #実行時間(s)
[1, 1, 0, 0, 0]

念のため確認してみて、

print(a.qubo)

[[-3  2  2  2  2]
 [ 0 -3  2  2  2]
 [ 0  0 -3  2  2]
 [ 0  0  0 -3  2]
 [ 0  0  0  0 -3]]

大きい数でやっても、

N=100
K=5

略

2.533233404159546
[0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1,
 0,
 0,
 0]

できたと思います。

関数として実装した

毎回使うので導入してみました。

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

2.212473154067993
[0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0]

数えてみましたがあってました。
大きな数でもやってみましたがOKでした。

量子ゲートでも使える

量子ゲートモデルのQAOAというアルゴリズムは量子アニーリングに近いことを実行していますので、同様のものを計算できます。
ここでは、Wildqatに加えて量子ゲートのSDKのBlueqatも手に入れる必要があります。

https://github.com/mdrft/Blueqat

量子ゲートでは、先ほどのQUBOをパウリ演算子の量子シミュレーションに置き換えますが、その書き換えはWildqatが自動的に行ってくれます。あとはBlueqatでの量子ゲートシミュレーションにかけるだけです。

import wildqat as wq 
from blueqat import vqe 

qubo = wq.pauli(wq.sel(4,1)) 
step = 4 
result = vqe.Vqe(vqe.QaoaAnsatz(qubo,step)).run() 
print(result.most_common(5))                                                                                                                  

(((1, 0, 0, 0), 0.2181742589469255), ((0, 1, 0, 0), 0.21817425894692538), ((0, 0, 1, 0), 0.21817425894692538), ((0, 0, 0, 1), 0.21817425894692533), ((0, 0, 0, 0), 0.03458645108329251))

出てきた答えの後ろの小数点の数字は回答の出る確率になっています。1が1つだけ選ばれている組み合わせが同一の確率で登場しているのがわかります。実機では状態ベクトルと呼ばれる確率を確認する機能が計算できますが、実機ではそれが計算できませんのでなんども計算をして確率分布を自分で求める必要があります。ここでは、状態ベクトルから出現確率を計算しています。

あわせて読みたい