はじめに
グローバーのアルゴリズムはよく検索に使われますが、データベースを効率的に探索が行えます。今回は実装をメインにこのグローバーの検索アルゴリズムを見ていきたいと思います。理論的な説明はwikipediaやその他たくさんの教科書で行われているので今回は式の途中に入れているもの以外は省略します。
参考：wiki
あとは、kyamazさんの説明がとてもいいので、こちらを参考に
全体の流れ
全体のアルゴリズムの流れを簡単にまとめます。
１、重ね合わせ状態を作る（すべての量子ビットにHゲートを適用）
２、マーキングと呼ばれる作業
３、振幅増幅反転と呼ばれる作業（これでほしい答えを浮かび上がらせる）
こちらを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が作れます。
from blueqat import Circuit
#振幅増幅反転
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})
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})
Counter({'01': 100})
#10回路
--H--S--*--S----H-X-*-X-H--
--H-----Z-------H-X-Z-X-H--
(Circuit(2).h[:].s[0].cz[0,1].s[0] + a).run(shots=100)
#Counter({'10': 100})
Counter({'10': 100})
#11回路
--H-----*-------H-X-*-X-H--
--H-----Z-------H-X-Z-X-H--
(Circuit(2).h[:].cz[0,1] + a).run(shots=100)
#Counter({'11': 100})
Counter({'11': 100})
このようにできました。
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({'110': 3,
'111': 82,
'100': 3,
'010': 3,
'011': 3,
'101': 2,
'000': 2,
'001': 2})
Counter({'111': 76,
'010': 3,
'001': 4,
'101': 8,
'100': 4,
'110': 1,
'011': 2,
'000': 2})
このように111ができました。Groverは精度を出すためには繰り返しが必要です。もう少し繰り返して見ます。
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': 92, '101': 2, '000': 3, '010': 1, '011': 1, '110': 1})
Counter({'111': 91,
'000': 2,
'101': 1,
'110': 2,
'011': 2,
'100': 1,
'010': 1})
精度が上がりました。十分な精度をとるためにはN量子ビットの場合で、√N必要みたいです。今回は3なので√3以上ですね。blueqatの改善と簡略化によって簡単に解けるようになりました。Groverが身近になりました。