@yuichirominato 2018.11.19更新 51views

BlueqatでGrover(グローバー)の検索アルゴリズムの実装

Blueqat Grover 検索 量子ゲート 量子コンピュータ

はじめに

グローバーのアルゴリズムはよく検索に使われますが、データベースを効率的に探索が行えます。今回は実装をメインにこのグローバーの検索アルゴリズムを見ていきたいと思います。理論的な説明はwikipediaやその他たくさんの教科書で行われているので今回は式の途中に入れているもの以外は省略します。

参考:wiki
https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%AD%E3%83%BC%E3%83%90%E3%83%BC%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

あとは、kyamazさんの説明がとてもいいので、こちらを参考に
https://qiita.com/kyamaz/items/37973effe783197291bc

全体の流れ

全体のアルゴリズムの流れを簡単にまとめます。

1、重ね合わせ状態を作る(すべての量子ビットにHゲートを適用)
2、マーキングと呼ばれる作業
3、振幅増幅反転と呼ばれる作業(これでほしい答えを浮かび上がらせる)

こちらをBlueqatで実装してみたいと思います。

簡単な例

まずは2量子ビットのGroverからです。4通りの組み合わせから11の組み合わせを抜き出してみたいと思います。グローバーのアルゴリズムでは、まず求めたい答えにマーキングを行います。マーキングの方法は簡単で、求めたい解に対応する状態ベクトルだけに-1がかかるようにします。マーキングはゲート操作を使います。

たとえば、00にマーキングしたい場合には、
[[-1,0,0,0],[0,1,0,0],[0,0,1,0,],[0,0,0,1]] = S[0],S[1],CZ[0,1],S[0],S[1]
というように、00の状態ベクトル[1,0,0,0]に対応する部分に-1を設定した行列をかけます。

01の時には、
[[1,0,0,0],[0,-1,0,0],[0,0,1,0,],[0,0,0,1]] = S[1],CZ[0,1],S[1]

10の時には、
[[1,0,0,0],[0,1,0,0],[0,0,-1,0,],[0,0,0,1]] = S[0],CZ[0,1],S[0]

11の時には、
[[1,0,0,0],[0,1,0,0],[0,0,1,0,],[0,0,0,-1]] = CZ[0,1]

こうすることによって対応する行列が実現できます。求めたい解に対するユニタリー変換を作り出す必要があります。
Sゲート、Hゲート、単位行列Iなどを用意して、


In [38]: print(np.kron(S,S)@np.kron(I,H)@cnot@np.kron(I,H)@np.kron(S,S))                                        
[[ 1.+0.00000000e+00j  0.-2.23711432e-17j  0.+0.00000000e+00j
   0.+0.00000000e+00j]
 [ 0.-2.23711432e-17j -1.+0.00000000e+00j  0.+0.00000000e+00j
   0.+0.00000000e+00j]
 [ 0.+0.00000000e+00j  0.+0.00000000e+00j -1.+0.00000000e+00j
   0.+2.23711432e-17j]
 [ 0.+0.00000000e+00j  0.+0.00000000e+00j  0.-2.23711432e-17j
  -1.+0.00000000e+00j]]

In [39]: print(np.kron(I,S)@np.kron(I,H)@cnot@np.kron(I,H)@np.kron(I,S))                                        
[[ 1.+0.00000000e+00j  0.-2.23711432e-17j  0.+0.00000000e+00j
   0.+0.00000000e+00j]
 [ 0.-2.23711432e-17j -1.+0.00000000e+00j  0.+0.00000000e+00j
   0.+0.00000000e+00j]
 [ 0.+0.00000000e+00j  0.+0.00000000e+00j  1.+0.00000000e+00j
   0.-2.23711432e-17j]
 [ 0.+0.00000000e+00j  0.+0.00000000e+00j  0.+2.23711432e-17j
   1.+0.00000000e+00j]]

In [40]: print(np.kron(S,I)@np.kron(I,H)@cnot@np.kron(I,H)@np.kron(S,I))                                        
[[ 1.00000000e+00+0.j -2.23711432e-17+0.j  0.00000000e+00+0.j
   0.00000000e+00+0.j]
 [-2.23711432e-17+0.j  1.00000000e+00+0.j  0.00000000e+00+0.j
   0.00000000e+00+0.j]
 [ 0.00000000e+00+0.j  0.00000000e+00+0.j -1.00000000e+00+0.j
   2.23711432e-17+0.j]
 [ 0.00000000e+00+0.j  0.00000000e+00+0.j -2.23711432e-17+0.j
   1.00000000e+00+0.j]]

In [41]: print(np.kron(I,H)@cnot@np.kron(I,H))                                                                  
[[ 1.00000000e+00 -2.23711432e-17  0.00000000e+00  0.00000000e+00]
 [-2.23711432e-17  1.00000000e+00  0.00000000e+00  0.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00  1.00000000e+00 -2.23711432e-17]
 [ 0.00000000e+00  0.00000000e+00  2.23711432e-17 -1.00000000e+00]]

となっています。また、振幅増幅反転のユニタリ変換は、対角項が-1、非対角項が+1の行列変換を用意して、


D = [[-1,1,1,1],[1,-1,1,1],[1,1,-1,1],[1,1,1,-1]]

これは振幅増幅反転のユニタリ変換として、既存ゲートを使って、下記のようにかけます。
H,X,CNOT(CZ)をつかって、


In [69]: print(np.kron(h,h)@np.kron(x,x)@np.array([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,-1]])@np.kron(x,x)@np.kron(h,h))                                                                                               
[[ 0.5 -0.5 -0.5 -0.5]
 [-0.5  0.5 -0.5 -0.5]
 [-0.5 -0.5  0.5 -0.5]
 [-0.5 -0.5 -0.5  0.5]]

In [48]: print(np.diag([-1,1,1,1])@np.kron(h,h)@np.array([1,0,0,0]))                                            
[-0.5  0.5  0.5  0.5]

In [49]: print(D@np.diag([-1,1,1,1])@np.kron(h,h)@np.array([1,0,0,0]))                                          
[1. 0. 0. 0.]

00の回路は、マーキングと振幅増幅反転まで加えて、


In [48]: print(np.diag([-1,1,1,1])@np.kron(h,h)@np.array([1,0,0,0]))                                            
[-0.5  0.5  0.5  0.5]

In [49]: print(D@np.diag([-1,1,1,1])@np.kron(h,h)@np.array([1,0,0,0]))                                          
[1. 0. 0. 0.]

01の回路は、


In [50]: print(np.diag([1,-1,1,1])@np.kron(h,h)@np.array([1,0,0,0]))                                            
[ 0.5 -0.5  0.5  0.5]

In [51]: print(D@np.diag([1,-1,1,1])@np.kron(h,h)@np.array([1,0,0,0]))                                          
[0. 1. 0. 0.]

10は、


In [52]: print(np.diag([1,1,-1,1])@np.kron(h,h)@np.array([1,0,0,0]))                                            
[ 0.5  0.5 -0.5  0.5]

In [53]: print(D@np.diag([1,1,-1,1])@np.kron(h,h)@np.array([1,0,0,0]))                                          
[0. 0. 1. 0.]

11は、


In [54]: print(np.diag([1,1,1,-1])@np.kron(h,h)@np.array([1,0,0,0]))                                            
[ 0.5  0.5  0.5 -0.5]

In [55]: print(D@np.diag([1,1,1,-1])@np.kron(h,h)@np.array([1,0,0,0]))                                          
[0. 0. 0. 1.]

振幅増幅反転のユニタリ変換は各パターン共通となっています。こちらをBlueqatに直してみます。

00の場合、


In [61]: Circuit().h[:].s[:].h[1].cnot[0,1].h[1].s[:].h[:].x[:].h[1].cnot[0,1].h[1].x[:].h[:].run()             
Out[61]: array([1.+0.j, 0.+0.j, 0.+0.j, 0.+0.j])

10の場合、


In [64]: Circuit().h[:].s[0].h[1].cnot[0,1].h[1].s[0].h[:].x[:].h[1].cnot[0,1].h[1].x[:].h[:].run()             
Out[64]: array([0.-0.j, 1.+0.j, 0.-0.j, 0.-0.j])

01の場合、


In [65]: Circuit().h[:].s[1].h[1].cnot[0,1].h[1].s[1].h[:].x[:].h[1].cnot[0,1].h[1].x[:].h[:].run()             
Out[65]: array([0.-0.j, 0.-0.j, 1.+0.j, 0.-0.j])

11の場合、


In [66]: Circuit().h[:].h[1].cnot[0,1].h[1].h[:].x[:].h[1].cnot[0,1].h[1].x[:].h[:].run()                       
Out[66]: array([0.-0.j, 0.-0.j, 0.-0.j, 1.+0.j])

これがGroverの検索アルゴリズムです。
回路で書くと、00の場合は、


--H-------*--------H-X---*---X-H--
--H-----H-X-H------H-X-H-X-H-X-H--

こちらは、最初が重ね合わせ。次がマーキング、最後が振幅増幅反転です。

3量子ビットの場合

続いて3量子ビットもやってみます。
CCNOT(CCXもしくはトフォリ)を使います。CCXの実装に関しては、この辺りを参照してくださいませ。
http://blog.mdrft.com/post/339

まず、マーキングの回路として、8つの状態ベクトルを操作する、np.diag([1,1,1,1,1,1,1,-1])という111だけを抜き出す回路を作ります。これは、CCXの最後のXをHで囲むこと、CCZに変換することで実現できます。


print(np.kron(np.kron(I,I),h)@CCNOT@np.kron(np.kron(I,I),h))                                           
[[ 1.00000000e+00 -2.23711432e-17  0.00000000e+00  0.00000000e+00
   0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00]
 [-2.23711432e-17  1.00000000e+00  0.00000000e+00  0.00000000e+00
   0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00  1.00000000e+00 -2.23711432e-17
   0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00 -2.23711432e-17  1.00000000e+00
   0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   1.00000000e+00 -2.23711432e-17  0.00000000e+00  0.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
  -2.23711432e-17  1.00000000e+00  0.00000000e+00  0.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   0.00000000e+00  0.00000000e+00  1.00000000e+00 -2.23711432e-17]
 [ 0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   0.00000000e+00  0.00000000e+00  2.23711432e-17 -1.00000000e+00]]

振幅増幅反転もH,XとCCZでつくれました。


print(np.kron(np.kron(h,h),h)@np.kron(np.kron(x,x),x)@np.kron(np.kron(I,I),h)@CCNOT@np.kron(np.kron(I,I),h)@np.kron(np.kron(x,x),x)@np.kron(np.kron(h,h),h))    
                                              
[[ 0.75 -0.25 -0.25 -0.25 -0.25 -0.25 -0.25 -0.25]
 [-0.25  0.75 -0.25 -0.25 -0.25 -0.25 -0.25 -0.25]
 [-0.25 -0.25  0.75 -0.25 -0.25 -0.25 -0.25 -0.25]
 [-0.25 -0.25 -0.25  0.75 -0.25 -0.25 -0.25 -0.25]
 [-0.25 -0.25 -0.25 -0.25  0.75 -0.25 -0.25 -0.25]
 [-0.25 -0.25 -0.25 -0.25 -0.25  0.75 -0.25 -0.25]
 [-0.25 -0.25 -0.25 -0.25 -0.25 -0.25  0.75 -0.25]
 [-0.25 -0.25 -0.25 -0.25 -0.25 -0.25 -0.25  0.75]]

Blueqatだとコードが長くなりすぎますので、コードを短くかけるようにリクエスト中です。
コンパクトにかけるようになったらまたおしらせします。

あわせて読みたい

SERVICE

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

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

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

詳しく見る

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

詳しく見る

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

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

COMMUNITY

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

CONNPASS SLACK

CONTACT

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

ブログトップに戻る

Recent Posts