@yuichirominato 2019.02.10更新 21views

【焼き直し】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はblueqatを利用します。

pip3 install blueqat
from blueqat import opt
a = opt.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()

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

[0, 0, 1, 1, 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 blueqat import opt
a = opt.opt()
a.qubo = [[-1,2,2],[0,-1,2],[0,0,-1]]
a.sa()
[0, 1, 0]

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

import numpy as np 

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, 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

略

[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]

できたと思います。

関数として実装した

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

from blueqat import opt
a = opt.opt()
a.qubo = opt.sel(20,10) #20から10選ぶ
a.sa()

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

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

量子ゲートでも使える

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

from blueqat import opt,vqe

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

(((0, 1, 0, 0), 0.1895196081954192), ((1, 0, 0, 0), 0.18951960819541913), ((0, 0, 1, 0), 0.1895196081954191), ((0, 0, 0, 1), 0.1895196081954191), ((0, 0, 0, 0), 0.14702076574218317))

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

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方