blueqat cloudで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というものを作れば、それを入力することで問題が解けます。ここで例題を５量子ビットから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に代入します。


from blueqat.wq import Opt
Opt().add([[-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]]).run()

[0, 0, 1, 1, 0]

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

[0, 1, 1, 0, 0]

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

一般化

上記行列には明らかにルールがあります。他の例で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になります。


Opt().add([[-1,2,2],[0,-1,2],[0,0,-1]]).run()
#[0, 0, 1]

[0, 1, 0]

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


import numpy as np 

N = 5
K = 2

Opt().add(np.diag([1-2*K]*N)+np.triu([[2] * N for i in range(N)],k=1)).run()
#[0, 1, 0, 1, 0]

[0, 0, 1, 0, 1]

量子ゲートでも使える

量子ゲートモデルのQAOAというアルゴリズムは量子アニーリングに近いことを実行していますので、同様のものを計算できます。このままできます。


result = Opt().add(np.diag([1-2*K]*N)+np.triu([[2] * N for i in range(N)],k=1)).qaoa()
print(result.most_common(5))
#(((0, 1, 0, 1, 0), 0.07565315862509445), ((1, 1, 0, 0, 0), 0.07565315862509443), ((1, 0, 1, 0, 0), 0.07565315862509443), ((1, 0, 0, 1, 0), 0.07565315862509443), ((0, 0, 1, 1, 0), 0.07565315862509443))

(((1, 0, 0, 1, 0), 0.06708667713096965), ((0, 1, 0, 1, 0), 0.0670866771309696), ((1, 0, 0, 0, 1), 0.0670866771309696), ((1, 0, 1, 0, 0), 0.06708667713096958), ((0, 1, 1, 0, 0), 0.06708667713096958))

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