Grover アルゴリズムについて

はじめに TL; DR;

このノートは, ある量子コンピューターの勉強会向けに作成したものです.
Qiita の Advent Calendar 2017 の 12/1 のエントリ記事です.

Grover アルゴリズムの概要

1996, Lov Grover, “A fast quantum mechanical algorithm for database search” quant-ph/9605043

Imagine a phone directory containing N names arranged in completely random order. In order to find someone’s phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only O(sqrt(N)) steps. The algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm.

完全にランダムな順序で並べられたN個の名前を含む電話帳を想像してみてください. 50%の確率で誰かの電話番号を見つけるためには, 古典的なアルゴリズム（決定論的であろうと確率的であろうと）は, 少なくとも N/2 名を見る必要があります. 量子力学的システムでは, 状態の重ね合わせにあり, 複数の名前を同時に調べることができます. さまざまな操作のフェーズを適切に調整することによって, 成功した計算は互いに強化し, 他はランダムに干渉します. その結果, 所望している電話番号は O(N−−√）$\mathcal{O}(\sqrt{N}）$ ステップだけで計算できます. このアルゴリズムは, 最も高速な量子力学アルゴリズムの定数倍の範囲の計算速度です.

グローバー自身が論文の abstracts で示しているとおり, グローバーアルゴリズムの用例として, 「整列化されていないアドレス帳から, 知り合いの携帯番号を探す」のに使われると,
一般的には「データベースの探索」と説明されています.
しかし, この具体例を想像しながらこのアルゴリズムを学ぶと, 少し戸惑うかもしれません. グローバーアルゴリズムは, 「逆関数の導出」と言うほうがより正確かもしれません.

すなわち, 量子コンピューターで処理できる関数 y=f(x)$y=f(x)$ があるとき, グローバーアルゴリズムを使うと, ある y$y$ を与える x$x$ の値を計算することができます.

例えば, 重ね合わせられた量子状態 ψ$\psi$ が特定の状態 x$x$ を含んでいる場合には, 1$1$ を返し, 含まない場合は 0$0$ を返すような関数 f(x,ψ)$f(x,\psi )$ を考えたとき,
x=ϕ$x=\varphi$ の答え f(ϕ,ψ)$f(\varphi ,\psi )$ が 0$0$ か, 1$1$ かを判定するときに, 使える最も効率的な量子アルゴリズム. これがグローバーアルゴリズムです.

4-qubit の例 :

のような ψ$\psi$ に, ϕ=|0101⟩$\varphi =|0101⟩$ が, 含まれるかどうかを調べる問題がこのアルゴリズムの対象です.

それでは, Grover アルゴリズムの特徴をみていきましょう.
Grover アルゴリズムは, 振幅増幅手法と呼ばれる操作を行い, 目的の値 x を検出します.

  振幅増幅手法 [Amplitude Amplification] :  
  欲しい解の確率振幅をマイナスにマーキングし, 全確率振幅の平均値の周りで逆転させる. 

2-qubit の例 :

　　　　　　|ϕ⟩=12(|00⟩+|01⟩+|10⟩+|11⟩)$|\varphi ⟩=\frac{1}{2}\left(|00⟩+|01⟩+|10⟩+|11⟩\right)$ という重ね合わせられた量子ビットがあるときに, この中から |10⟩$|10⟩$ を探したいという問題とします.

手順１） 欲しい解の確率振幅をマイナスにマーキング

　　　　　　|ϕ⟩marked=12(|00⟩+|01⟩−|10⟩+|11⟩)$|\varphi {⟩}_{marked}=\frac{1}{2}\left(|00⟩+|01⟩-|10⟩+|11⟩\right)$

手順２） 全確率振幅の平均値の周りで逆転

　　　　　マーキングされた状態の全確率振幅 ⟨α⟩$⟨\alpha ⟩$ は, (12+12−12+12)/4=14$\left(\frac{1}{2}+\frac{1}{2}-\frac{1}{2}+\frac{1}{2}\right)/4=\frac{1}{4}$ です.

　　　　　|ϕ⟩′marked=(14−12+14)|00⟩+(14−12+14)|01⟩+(14+12+14)|10⟩+(14−12+14)|11⟩=|10⟩$|\varphi {⟩}_{marked}^{\mathrm{\prime }}=\left(\frac{1}{4}-\frac{1}{2}+\frac{1}{4}\right)|00⟩+\left(\frac{1}{4}-\frac{1}{2}+\frac{1}{4}\right)|01⟩+\left(\frac{1}{4}+\frac{1}{2}+\frac{1}{4}\right)|10⟩+\left(\frac{1}{4}-\frac{1}{2}+\frac{1}{4}\right)|11⟩=|10⟩$

　　　　　この状態 |ϕ⟩′marked$|\varphi {⟩}_{marked}^{\mathrm{\prime }}$ を観測すると, |10⟩$|10⟩$ の確率が 1$1$ となり, |10⟩$|10⟩$ の状態を探しだすことができます.

2-qubit では, この手順１）, ２）を１回行えば, マーキングされた量子状態の確率振幅が 1 になりますが, N-qubit のときには, この方法を反復してマーキングした振幅を増幅します.

また, 問題の初期量子状態に探したい状態がわずかな確率で含まれている場合でも, 次の例のように, この手法は有効に作用します.

2-qubit の例（わずかな確率で検索対象が含まれている例） :

　（問題）　|ϕ⟩=4003√1201|00⟩+4003√1201|01⟩+491201|10⟩+4003√1201|11⟩$|\varphi ⟩=\frac{400\sqrt{3}}{1201}|00⟩+\frac{400\sqrt{3}}{1201}|01⟩+\frac{49}{1201}|10⟩+\frac{400\sqrt{3}}{1201}|11⟩$

　　　　　　|ϕ⟩=0.0407⋯|10⟩+0.5768⋯(|00⟩+|01⟩+|11⟩)$|\varphi ⟩=0.0407\cdots |10⟩+0.5768\cdots \left(|00⟩+|01⟩+|11⟩\right)$

　　　　　　問題の |10⟩$|10⟩$ の確率は, (0.0407⋯)2≈0.166%${\left(0.0407\cdots \right)}^2\approx 0.166\mathrm{\%}$

　（手順１）|ϕ⟩marked=4003√1201|00⟩+4003√1201|01⟩−491201|10⟩+4003√1201|11⟩$|\varphi {⟩}_{marked}=\frac{400\sqrt{3}}{1201}|00⟩+\frac{400\sqrt{3}}{1201}|01⟩-\frac{49}{1201}|10⟩+\frac{400\sqrt{3}}{1201}|11⟩$

　　　　　　全確率振幅平均は, ⟨α⟩=12003√−491201×4$⟨\alpha ⟩=\frac{1200\sqrt{3}-49}{1201\times 4}$

　（手順２）|ϕ⟩′marked=4003√−491201×2|00⟩+4003√−491201×2|01⟩+12003√+491201×2|10⟩+4003√−491201×2|11⟩$|\varphi {⟩}_{marked}^{\mathrm{\prime }}=\frac{400\sqrt{3}-49}{1201\times 2}|00⟩+\frac{400\sqrt{3}-49}{1201\times 2}|01⟩+\frac{1200\sqrt{3}+49}{1201\times 2}|10⟩+\frac{400\sqrt{3}-49}{1201\times 2}|11⟩$

　　　　　　|ϕ⟩′marked=12003√+491201×2|10⟩+4003√−491201×2(|00⟩+|01⟩+|11⟩)$|\varphi {⟩}_{marked}^{\mathrm{\prime }}=\frac{1200\sqrt{3}+49}{1201\times 2}|10⟩+\frac{400\sqrt{3}-49}{1201\times 2}\left(|00⟩+|01⟩+|11⟩\right)$

　　　　　　|ϕ⟩′marked=0.8857⋯|10⟩+0.2680⋯(|00⟩+|01⟩+|11⟩)$|\varphi {⟩}_{marked}^{\mathrm{\prime }}=0.8857\cdots |10⟩+0.2680\cdots \left(|00⟩+|01⟩+|11⟩\right)$

　　　　　　操作後の |10⟩$|10⟩$ の確率は, (0.8857⋯)2≈78.44%${\left(0.8857\cdots \right)}^2\approx 78.44\mathrm{\%}$

Grover’s Search Algorithm の数理

f(x):={10(x=z)(x≠z),x∈Z$f(x):=\{\begin{array}{ll}1& (x=z)\\ 0& (x\ne z)\end{array},x\in \mathbb{Z}$ を考えるとき, 次の 2 つのオペレーター行列を考えます.

【オペレーター Rf$R_f$ ：選択的回転】
　　　　　　Rf(m,n):=eiπf(x)δmn=(−1)f(x)δmn=I−2|z⟩⟨z|$R_f(m,n):=e^{i\pi f(x)}{\delta }_{mn}=(-1{)}^{f(x)}{\delta }_{mn}=\mathcal{I}-2|z⟩⟨z|$

【オペレーター D$D$ ：平均値まわりの反転】
　　　　　　D:=−I+2|ϕ0⟩⟨ϕ0|$D:=-\mathcal{I}+2|{\varphi }_0⟩⟨{\varphi }_0|$
　　　　　　ここでの, |ϕ0⟩=1N−−√∑x=0N−1|x⟩${\displaystyle |{\varphi }_0⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩}$

ここで, 選択的回転 Rf$R_f$ と, 平均値まわりの反転 D$D$ の合成を考えると,

　　　　　　Uf:=DRf=(−I+2|ϕ0⟩⟨ϕ0|)(I−2|z⟩⟨z|)$U_f:=D{R}_f=\left(-\mathcal{I}+2|{\varphi }_0⟩⟨{\varphi }_0|\right)\left(\mathcal{I}-2|z⟩⟨z|\right)$

これを, 状態 |ϕ⟩:=∑x=0N−1wx|x⟩${\displaystyle |\varphi ⟩:=\sum _{x=0}^{N-1}{w}_x|x⟩}$ ここで, (∑x=0N−1|wx|2=1)${\displaystyle \left(\sum _{x=0}^{N-1}|w_x{|}^2=1\right)}$ に施すと,

状態 |ϕ⟩$|\varphi ⟩$ は, 次で示す状態に遷移します.

　　　　　　Uf|ϕ⟩=∑x=0,x≠zN−1(2w¯¯¯¯−wx)|x⟩+(2w¯¯¯¯+wz)|z⟩${\displaystyle U_f|\varphi ⟩=\sum _{x=0,x\ne z}^{N-1}(2\overline{w}-w_x)|x⟩+(2\overline{w}+w_z)|z⟩}$

すなわち, 目的の |z⟩$|z⟩$ の確率振幅が増加し, それ以外の |x⟩,(x≠z)$|x⟩,(x\ne z)$ では確率振幅が減少します.
目的の |z⟩$|z⟩$ の確率振幅が十分に大きくなるまで, この操作 Uf$U_f$ を繰り返します.

反復回数についての考察

次に, どの程度の回数を繰り返せばよいかを考察します.
操作 Uf$U_f$ を繰り返す回数を k$k$ として, k$k$ 回の Uf$U_f$ の操作をまとめて, Ukf$U_f^k$ とおきます.

ここで, |ϕ⟩$|\varphi ⟩$ として, 平均値まわりの反転のときに使った |ϕ0⟩$|{\varphi }_0⟩$ を考えてみます.
状態 |ϕ0⟩$|{\varphi }_0⟩$ に Ukf$U_f^k$ を施すと,

sinθ=1N−−−√,cosθ=1−1N−−−−−−√${\displaystyle sin\theta =\sqrt{\frac{1}{N}},cos\theta =\sqrt{1-\frac{1}{N}}}$ とおいて,

　　　　　　Ukf|ϕ0⟩=sin((2k+1)θ)|z⟩+∑x≠zN−11N−1−−−−−√cos((2k+1)θ)|x⟩${\displaystyle U_f^k|{\varphi }_0⟩=sin((2k+1)\theta )|z⟩+\sum _{x\ne z}^{N-1}\frac{1}{\sqrt{N-1}}cos((2k+1)\theta )|x⟩}$

となります.

m:=⌊π4θ⌋$m:=\lfloor \frac{\pi }{4\theta }\rfloor$ とおき, Uf$U_f$ を m$m$ 回施して観測したときに期待どおりの結果が得られる確率 Pc$P_c$ とすると,

　　　　　　Pc≥1−1N$P_c\ge 1-\frac{1}{N}$

で抑えられ, このとき,

　　　　　　m=O(N−−√）$m=\mathcal{O}(\sqrt{N}）$

です.

具体的な例として「|ϕ⟩=12(|00⟩+|01⟩+|10⟩+|11⟩)$|\varphi ⟩=\frac{1}{2}\left(|00⟩+|01⟩+|10⟩+|11⟩\right)$ で表された量子ビット状態があるときに, この中から |11⟩$|11⟩$ を探したい」という問題を考えます.

手順１）欲しい解の確率振幅をマイナスにマーキング

　　　　　　CZ(Controlled−Z)$CZ(Controlled-Z)$ オペレータを作用させれば, |11⟩$|11⟩$ の符号を入れ替えられます.

　　　　　　22×22$2^2\times 2^2$ の行列で表すと, CZ=(I00Z)$CZ=\left(\begin{array}{cc}I& 0\\ 0& Z\end{array}\right)$ . ここでの I,Z$I,Z$ は,それぞれ I=(1001),Z=(100−1)$I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),Z=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)$ の 2×2$2\times 2$ の行列.

　　　　　　この行列 CZ$CZ$ を |ϕ⟩$|\varphi ⟩$ に作用すると,

　　　　　　CZ|ϕ⟩=12(|00⟩+|01⟩+|10⟩−|11⟩)$CZ|\varphi ⟩=\frac{1}{2}\left(|00⟩+|01⟩+|10⟩-|11⟩\right)$

手順２）全確率振幅の平均値の周りで逆転

　　　　　　D=12⎛⎝⎜⎜⎜−11111−11111−11111−1⎞⎠⎟⎟⎟=12(X−IX+IX+IX−I)=−12–√(HHH−H)(0XX0)(I00Z)(0XX0)12–√(HHH−H)${\displaystyle D=\frac{1}{2}\left(\begin{array}{cccc}-1& 1& 1& 1\\ 1& -1& 1& 1\\ 1& 1& -1& 1\\ 1& 1& 1& -1\end{array}\right)=\frac{1}{2}\left(\begin{array}{cc}X-I& X+I\\ X+I& X-I\end{array}\right)=\frac{-1}{\sqrt{2}}\left(\begin{array}{cc}H& H\\ H& -H\end{array}\right)\left(\begin{array}{cc}0& X\\ X& 0\end{array}\right)\left(\begin{array}{cc}I& 0\\ 0& Z\end{array}\right)\left(\begin{array}{cc}0& X\\ X& 0\end{array}\right)\frac{1}{\sqrt{2}}\left(\begin{array}{cc}H& H\\ H& -H\end{array}\right)}$

最終的な右辺には, -1 が全体に掛かっています. これは, グローバル位相, または絶対位相 （global phase）と呼んでいます. グローバル位相は, 測定段階で絶対値の二乗をとるため, 量子計算としては, +1 との区別ができません. そのため, 一般的に無視しても良いとされています. 量子回路にする以降の例ではこの -1 は省略して検証を進めます.

　　　　　　D⋅CZ|ϕ⟩=14((−1+1+1−1)⋅|00⟩+(1−1+1−1)⋅|01⟩+(1+1−1−1)⋅|10⟩+(1+1+1+1)⋅|11⟩)$D\cdot CZ|\varphi ⟩=\frac{1}{4}\left((-1+1+1-1)\cdot |00⟩+(1-1+1-1)\cdot |01⟩+(1+1-1-1)\cdot |10⟩+(1+1+1+1)\cdot |11⟩\right)$

ここで, Z=H⋅X⋅H$Z=H\cdot X\cdot H$ を使うと, CZ=(I⊗H)⋅CX⋅(I⊗H)$CZ=(I\otimes H)\cdot CX\cdot (I\otimes H)$ と書けます.

IBM Q を使って検証

これを IBM Q 上で表現すると以下のようになります. 実行すると, |11⟩$|11⟩$ の確率が 1$1$ となります.

次に 3-qubit の例は以下のようになります.

＊ 3-qubit で |111⟩$|111⟩$ を 1$1$ 回の試行を行なう例

＊ 3-qubit で |111⟩$|111⟩$ を 2$2$ 回の試行を行なう例

【補足】 手順２）の別解

手順２での行列の式の変換は, 執筆者の力では導出が難しく, 参考書のお手本を元にしております. 執筆者の行なった違う計算を次に記します.

　　D=12(X−IX+IX+IX−I)${\displaystyle D=\frac{1}{2}\left(\begin{array}{cc}X-I& X+I\\ X+I& X-I\end{array}\right)}$
　　
　　この行列の固有値を λ$\lambda$ とすると, 固有値を求める式は,
　　
　　4λ2−4(X−I)λ+(X−I)2−(X+I)2=0$4{\lambda }^2-4\left(X-I\right)\lambda +{\left(X-I\right)}^2-{\left(X+I\right)}^2=0$
　　4λ2−4(X−I)λ−4⋅X=0$4{\lambda }^2-4\left(X-I\right)\lambda -4\cdot X=0$
　　(λ+I)(λ−X)=0$\left(\lambda +I\right)\left(\lambda -X\right)=0$ となり,
　　
　　固有値は, λ=−I,X$\lambda =-I,X$ . λ=−I$\lambda =-I$ の固有ベクトルは, 12√(I−I)$\frac{1}{\sqrt{2}}\left(\begin{array}{c}I\\ -I\end{array}\right)$ . λ=X$\lambda =X$ の固有ベクトルは, 12√(II)$\frac{1}{\sqrt{2}}\left(\begin{array}{c}I\\ I\end{array}\right)$ です.
　　
　　ここで, 固有値ベクトルで作られる行列 　　U=12√(III−I)$U=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}I& I\\ I& -I\end{array}\right)$ を考えると,
　　これは, 2×2$2\times 2$ 行列の Hadamard 演算子 H$H$ を使って, H⊗I$H\otimes I$ と表せます.
　　また, この U$U$ は, 逆行列も同じ行列 U−1=U$U^{-1}=U$ という特徴もあり, この性質を使って,
　　
　　U−1DU=(H⊗I)⋅D⋅(H⊗I)=(X00−I)$U^{-1}DU=\left(H\otimes I\right)\cdot D\cdot \left(H\otimes I\right)=\left(\begin{array}{cc}X& 0\\ 0& -I\end{array}\right)$
　　が得られます.
　　
　　次に, 右辺の (X00−I)$\left(\begin{array}{cc}X& 0\\ 0& -I\end{array}\right)$ の展開を考えてみます.
　　形が CNOT=(I00X)$CNOT=\left(\begin{array}{cc}I& 0\\ 0& X\end{array}\right)$ に似ていますので, 単にこの２つをかけてみます.

　　(X00−I)⋅(I00X)=(X00−X)=Z⊗X$\left(\begin{array}{cc}X& 0\\ 0& -I\end{array}\right)\cdot \left(\begin{array}{cc}I& 0\\ 0& X\end{array}\right)=\left(\begin{array}{cc}X& 0\\ 0& -X\end{array}\right)=Z\otimes X$ 　　
　　偶然にもうまく量子回路にできる形がでてきました. そこで, 両辺に, CNOT を掛けると次式が得られます.

　　(X00−I)=(Z⊗X)⋅CNOT$\left(\begin{array}{cc}X& 0\\ 0& -I\end{array}\right)=\left(Z\otimes X\right)\cdot CNOT$ 　　
　　この式を使って, U−1DU$U^{-1}DU$ の左右から, U=U−1=H⊗I$U=U^{-1}=H\otimes I$ を掛けると, D$D$ を表す式が得られます.

　　D=(H⊗I)⋅(Z⊗X)⋅CNOT⋅(H⊗I)$D=\left(H\otimes I\right)\cdot \left(Z\otimes X\right)\cdot CNOT\cdot \left(H\otimes I\right)$
　　
　　これを IBM Q 上で表現すると以下のようになります.

(Rigetti製) pyquil を使って検証

python環境に pyquil をインストールします.

$ pip install pyquil

＊ 2-qubit から, |11⟩$|11⟩$ があるか検索する量子プログラム.

import pyquil.quil as pq
import pyquil.api as api
from pyquil.gates import *
qvm = api.SyncConnection()
p = pq.Program()
p.inst(
  H(0),
  H(1),
  H(0),
  CNOT(1,0),
  H(0),
  H(0),
  H(1),
  X(0),
  X(1),
  H(0),
  CNOT(1,0),
  H(0),
  X(0),
  X(1),
  H(0),
  H(1),
  MEASURE(0, 0),
  MEASURE(1, 1))
result = qvm.run(p,[0,0],20)
print(result)

Grover の応用

• 複数の検索対象を同時に見つけ出すための探索 := G-BBHT

  Boyer, M., Brassard, G., Hoyer, P., Tapp, A. 1996 Tight bounds on quantum searching. In Fourth Workshop on Physics and Computation
  (ed. T. Toffoli & M. Biaford & J. Leao), pp. 36-43. New England Complex Systems Institute.

• p=4k+1$p=4k+1$ の素数の探索 Quantum Computation of Prime Number Functions (arxiv:1302.6245)

  |i⟩$|i⟩$ の i$i$ が素数なら, −1$-1$ , 合成数なら 1$1$ を返すようなオラクルを考える.

書籍紹介

量子コンピューターを勉強するために, お薦めの図書を教えてほしいとよく質問されます.
今回, Grover アルゴリズムに関して, 市販されている書籍で調べてこの資料を記しました. 同じ課題について調べたことで, それぞれの図書の特徴が知れると思い, 下表にまとめました.

＊	表紙	タイトル	説明（Groverアルゴリズムに関する記載について）
◎		量子コンピュータと量子通信〈2〉量子コンピュータとアルゴリズム Michael A. Nielsen/ Isaac L. Chuang (著) 木村 達也 (訳), オーム社 ￥3,800, 2005/1/10	量子コンピューターの最も著名な教科書. Grover アルゴリズムに関しては, 第６章「量子探索アルゴリズム」で 32ページにわたり解説. 後半の章では, 量子コンピューターの物理的実現方法について書かれています.
◎		量子アルゴリズム 中山 茂 (著), 技報堂出版 ￥5,400, 2014/10/30	Grover アルゴリズムは, 第１２章「量子探索アルゴリズム」（18ページ）のなかで解説. 量子状態の確率振幅が増大していく図が分かりやすい. また, 8 個（3 qubit）の量子回路の具体的な記載があり, 行列式や量子ビット状態の時間発展が分かりやすい. 同じ著者の “クラウド量子計算入門” の理論面を補填するためにはよい.
◎		クラウド量子計算入門 中山 茂 (著), カットシステム ￥5,500, 2016/10/10	第１３章「グローバーの探索問題の量子実験」（13ページ）で Grover アルゴリズムを具体的に IBM Q を使って, 量子回路にしながら解説しています. 本書全般にわたり, IBM Q の利用を想定されており, 具体的な回路を使いながら, 理論的な解説をしているのが特徴.
○		量子コンピュータの基礎数理 上坂 吉則 (著), コロナ社 ￥3,000, 2000/5/26	第６章「ファイル検索」（22ページ）で Grover アルゴリズムを解説. 全般的に数式を用いて説明されており, 数理的な説明の方が分かりやすい方にはよい. 前半の章では, 量子ゲートの例もあるが, Grover アルゴリズムなどの量子アルゴリズムに関しては, 具体的な量子回路の記載がなく, 実用例を考えるには不向き. 理論寄り.
○		今度こそわかる量子コンピューター 西野 友年 (著), 講談社 ￥2,900, 2015/10/23	第１３章「量子検索」（14ページ）が Grover アルゴリズムの解説. 数式も少なめに抑えて, 平易な例を挙げるなど理解しやすいように工夫されている. ただし, 理論的な説明は十分ではありません. ほかの章でも同じように平易に書かれており, 取り扱っている範囲も広範.
○		量子情報科学入門 石坂 智/ 小川 朋宏/ 河内 亮周/ 木村 元/ 林 正人 (著), 共立出版 ￥3,800, 2012/6/10	「量子アルゴリズム」の章に紹介された幾つかのアルゴリズムの１つとして紹介されています. （「Grover のアルゴリズム」の項. 10ページ）定理の定義やその証明の記載があり, 数理的説明. 記載されている内容の範囲も多く, 数式と文章での説明のバランスがよい.
○		量子計算 (ナチュラルコンピューティング・シリーズ) 西野 哲朗/ 三原 孝志/ 岡本 龍明 (著) 萩谷 昌己/ 横森 貴 (編) , 近代科学社 ￥4,500, 2015/10/13	第３章「量子デジタル計算」の１節「Grover のアルゴリズム」（12ページ）で解説.
△		量子情報理論 第2版 佐川 弘幸/ 吉田 宣章 (著) , 丸善出版 ￥3,500, 2012/3/30	第８章「量子検索アルゴリズム」（12ページ）で Grover アルゴリズムを解説. 3量子ビットの例題で, 具体的な 8x8 行列の記載が特徴的. 量子回路等の記載はない. 全ての章に演習問題があり, その解答も巻末にあり, 初心者にはわかりやすい.
△		マーミン 量子コンピュータ科学の基礎 N. David Mermin (著) 木村 元 (訳), 丸善 ￥4,800, 2009/7/30	第４章（12ページ）が Grover アルゴリズムについての解説. 「W$W$ の構成法」が特徴的. 特定する数が複数ある場合への一般化にも言及あり. 最新の量子計算からみると, 少し古い印象です.
△		量子コンピューティング Jozef Gruska (著) 伊藤 正美/ 岩本 宙造/ 森田 憲一/ 今井 克暢/ 外山 政文 (訳) , 森北出版 ￥8,000, 2003/11/19	Grover アルゴリズムは, 第３章「アルゴリズム」の中で, 「量子探索と数え上げ」（13ページ）の項として解説. 検索対象 x が複数である G-BBHT 探索アルゴリズムの説明が多い. 数え上げ問題の計算量の古典アルゴリズムとの比較表が特徴的. 全般にわたり, 練習問題による問題提起があるものの, その問題の明確な回答がなく, 自力で解法が見つけられないと辛い内容です.
△		量子計算と量子情報の原理 G.ベネンティ (著) 広岡 一 (訳), 丸善出版 ￥5,000, 2012/6/5	第３章「量子計算」の１節（8ページ）で Grover アルゴリズムを扱っています. 量子計算の基礎から応用の導入まで, それぞれの話題がコンパクトかつ広範に取り上げられています.
△		量子情報工学 富田 章久 (著), 森北出版 ￥3,400, 2017/2/28	Grover アルゴリズムを一般化した「振幅増幅」を解説し, その例として Grover アルゴリズムを紹介しています. （振幅増幅の説明から5ページ）
ー		観測に基づく量子計算 小柴 健史/ 藤井 啓祐/ 森前 智行 (著), コロナ社 ￥2,800, 2017/3/10	測定型量子計算に関する基礎から応用までカバーした良書. Groverアルゴリズムとは異なる高度な分野を扱っており, Groverアルゴリズムの記載はありません. OpenQLプロジェクトに参加されている藤井さんが執筆されています.
ー		量子計算理論 量子コンピュータの原理 森前 智行 (著), 森北出版 ￥3,600, 2017/11/14	計算量に関する説明がメインで, BQPの定義や超量子計算, 非ユニバーサル計算など前衛的な内容. Grover アルゴリズムなどの基礎的な理論の記述はありません.
ー		個別量子系の物理 ─イオントラップと量子情報処理 占部 伸二 (著) , 朝倉書店 ￥4,000, 2017/10/15	量子計算の基礎的な内容はなく, イオントラップ方式の量子コンピューターを実現するための物理系の数理を扱っています. Grover, Shor などのアルゴリズムの記載はありません.
ー		量子コンピュータ入門(第2版) 宮野 健次郎/ 古澤 明 (著), 日本評論社 ￥2,500, 2016/3/10	Shor アルゴリズムについては, １つの章をかけて詳しい解説がありますが, 残念ながら Grover アルゴリズムについては, 記述がありませんでした. 光を用いた量子テレポーテーションの章が特徴的.
ー		入門量子コンピュータ Gennady P. Berman/ Ronnie Mainieri/ Gary D. Doolen/ Vladimir I. Tsifrinovich (著) 松田 和典 (訳), パーソナルメディア ￥2,800, 2002/9/10	Grover アルゴリズムや Shor アルゴリズムに関する記述はありません, イオントラップや核スピンなど, 量子コンピューターを実現するための物理系と関連する解説が多いです.
ー		量子プログラミングの基礎 Mingsheng Ying (著) 川辺 治之 (訳), 共立出版 ￥6,500, 2017/3/31	古典 while 言語の量子プログラミングへの拡張が特徴的. Groverアルゴリズムの言及はありません.
ー		量子情報の物理―量子暗号、量子テレポーテーション、量子計算 D.Bouwmeester (著) 小芦 雅斗/ 西野 哲朗/ 井元 信之 (訳) , 共立出版 ￥5,300, 2007/5/25	Grover アルゴリズムについては, NP問題との関連で 3ページで紹介されている程度. 理論や具体的な計算の記述はありません.
ー		量子情報科学の基礎―量子コンピュータへのアプローチ 広田 修 (著), 森北出版 ￥3,600, 2002/4/15	Grover アルゴリズムについての記述はありません. 量子コンピューター発展に至る歴史的な考察や, エンタングルメントに関する解説が多い.
？		量子コンピュータの理論―量子コンピューティング入門 西野 哲朗 (著), 培風館 （入手困難）, 2002/12	ー
？		量子コンピューティング―量子コンピュータの実現へ向けて Colin P. Williams/ Scott H. Clearwater (著) 西野 哲朗/ 渡辺 昇/ 荒井 隆 (訳), シュプリンガー （入手困難）, 2000/06	ー

（＊）オススメ度

付録: sympy で Grover アルゴリズムを計算してみましょう

まず, python環境に sympy をインストールします.

$ pip install sympy

sympy.physics.quantum パッケージをインポートします.

>>> from sympy.physics.quantum import *
>>> from sympy.physics.quantum.gate import X,Y,Z,H,T,S,CNOT,SWAP
>>> from sympy.physics.quantum.qubit import Qubit

＊ 2-qubit から, |11⟩$|11⟩$ があるか検索する量子プログラム.

>>> qi = qapply(H(0)*H(1)*Qubit('00'))
>>> rf_3 = H(0)*CNOT(1,0)*H(0)
>>> d_2  = (H(0)*H(1))*(X(0)*X(1))*(H(0)*CNOT(1,0)*H(0))*(X(0)*X(1))*(H(0)*H(1))
>>> grover = d_2 * rf_3
>>> qapply( grover * qi)
-|11>

別解したグローバル位相が +1 のケースの用例も記します.

>>> from sympy.physics.quantum.gate import IdentityGate as I
>>> qi = qapply(H(0)*H(1)*Qubit('00'))
>>> rf_3 = H(0)*CNOT(1,0)*H(0)
>>> d_2 = (H(1)*I(0))*(Z(1)*X(0))*CNOT(1,0)*(H(1)*I(0))   # 別解の行列
>>> grover = d_2 * rf_3
>>> qapply( grover * qi)
|11>               # ←グローバル位相が正の値

更新記録

2017/11/15 初版
2017/11/27 追記
2017/12/01 Advent Calendar 2017 の「はじめに」を追記