@yuichirominato 2019.01.26更新 298views

【焼き直し】Grover(グローバー)のアルゴリズム


はじめに

効率的に探索を行うグローバーのアルゴリズムを簡単にかけるように改良しました。Blueqatを使ってやって見ましょう。元の記事は下記です。

https://blog.mdrft.com/post/442

概要

グローバーのアルゴリズムは未整序のデータの検索が高速にできるというアルゴリズムです。マーキングの部分にあたるオラクルと呼ばれる関数部分に検索のアルゴリズムを入れましょう。

全体の流れは、

1、重ね合わせ
2、探したいデータのマーキング
3、マーキングを可視化する振幅増幅反転

-|重ね合わせ|-|マーキング|-|振幅増幅反転|-|マーキング|-|振幅増幅反転|-

マーキングと振幅増幅反転を繰り返すと精度が上がります。こちらをBlueqatで実装してみたいと思います。

マーキングの数理

まず2量子ビットのGroverからです。2量子ビットの組み合わせの場合の数は、00,01,10,11の4通りです。その中から特定の組み合わせを抜き出してみたいと思います。それを実現するにはゲート操作をつかって、「解に対応する状態ベクトルだけに-1がかかる対角行列を数学的に作り」ます。

#00
[[-1  0  0  0]
 [ 0  1  0  0]
 [ 0  0  1  0]
 [ 0  0  0  1]]

#01
[[ 1  0  0  0]
 [ 0 -1  0  0]
 [ 0  0  1  0]
 [ 0  0  0  1]]

#10
[[ 1  0  0  0]
 [ 0  1  0  0]
 [ 0  0 -1  0]
 [ 0  0  0  1]]

#11
[[ 1  0  0  0]
 [ 0  1  0  0]
 [ 0  0  1  0]
 [ 0  0  0 -1]]

このように、マーキングしたい状態ベクトルに対応する部分に-1を設定した行列を作ってかけます。

マーキングを実装

マーキング回路は下記のように重ね合わせの後に上記のゲートをかけます。下記のようにHのあとに各々のオラクルをつけます。*はコントロールゲート、Zはターゲットゲートです。対応するblueqatコードも併記します。

#00
--H--S--*--S--
--H--S--Z--S--

Circuit(2).h[:].s[:].cz[0,1].s[:]

#01
--H-----*-----
--H--S--Z--S--

Circuit(2).h[:].s[1].cz[0,1].s[1]

#10
--H--S--*--S--
--H-----Z-----

Circuit(2).h[:].s[0].cz[0,1].s[0]

#11
--H-----*-----
--H-----Z-----

Circuit(2).h[:].cz[0,1]

振幅増幅反転の数理

振幅増幅反転は、対角項が-1、非対角項が+1の行列を用意することでマーキングした回路にかけることで、マーキングしたものの振幅が増幅されます。振幅増幅反転のユニタリ変換は各パターン共通となっています。こちらをBlueqatに直してみます。

Circuit(2).h[:].x[:].cz[0,1].x[:].h[:].m[:]

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

これで上記の対角項が-1、非対角項が+1の行列を作ることができます。先ほどのマーキングと合わせることで簡単に実装ができます。

Groverのアルゴリズムの実装

ということで簡単にGroverが作れます。

#振幅増幅反転
a = Circuit(2).h[:].x[:].cz[0,1].x[:].h[:].m[:]

#00回路
--H--S--*--S----H-X-*-X-H--
--H--S--Z--S----H-X-Z-X-H--

(Circuit(2).h[:].s[:].cz[0,1].s[:] + a).run(shots=100)
Counter({'00': 100})

#01回路
--H-----*-------H-X-*-X-H--
--H--S--Z--S----H-X-Z-X-H--

(Circuit(2).h[:].s[1].cz[0,1].s[1] + a).run(shots=100)
Counter({'01': 100})

#10回路
(Circuit(2).h[:].s[0].cz[0,1].s[0] + a).run(shots=100)
Counter({'10': 100})
--H--S--*--S----H-X-*-X-H--
--H-----Z-------H-X-Z-X-H--

#11回路
(Circuit(2).h[:].cz[0,1] + a).run(shots=100)
Counter({'11': 100})
--H-----*-------H-X-*-X-H--
--H-----Z-------H-X-Z-X-H--

このようにできました。

3量子ビットの場合

ccxゲートを使います。マーキングは同様に必要なデータのところに-1がかかるようにして、振幅増幅反転も対角項がプラス、非対角項がマイナスの行列を作ります。ccxとhとxで作れます。111を選ぶ回路は、

#振幅増幅反転
b = Circuit(3).h[:].x[:].h[2].ccx[0,1,2].h[2].x[:].h[:].m[:]

#111のマーキングを組み合わせて
(Circuit(3).h[:].h[2].ccx[0,1,2].h[2] + b).run(shots=100)

Counter({'111': 76,
         '010': 3,
         '001': 4,
         '101': 8,
         '100': 4,
         '110': 1,
         '011': 2,
         '000': 2})

このように111ができました。Groverは精度を出すためには繰り返しが必要です。もう少し繰り返して見ます。

#111のマーキング
b = Circuit(3).h[2].ccx[0,1,2].h[2]
#振幅増幅反転
c = Circuit(3).h[:].x[:].h[2].ccx[0,1,2].h[2].x[:].h[:]

d = b+c

#111のマーキングを組み合わせて二回繰り返しで、
(Circuit(3).h[:] +d+d).m[:].run(shots=100)

Counter({'111': 91,
         '000': 2,
         '101': 1,
         '110': 2,
         '011': 2,
         '100': 1,
         '010': 1})

精度が上がりました。十分な精度をとるためにはN量子ビットの場合で、√N必要みたいです。今回は3なので√3以上ですね。blueqatの改善と簡略化によって簡単に解けるようになりました。Groverが身近になりました。

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

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

BlueqatSDKの使い方