論文メモ：Generalized Grover Search Algorithm for Arbitary Inital Amplitude Distribution
1 Intorduction
N個の中からr個を探索するためのGrover's algorithmのt step後の振幅の大きさの式は，Boyerらによって与えられた．この式は，初期状態が一様であることを仮定している．初期状態が一様でない場合，つまり，実数または複素数の任意の振幅を初期状態で始めるGrover's alogrithmを解析するのがこの論文の目的．この論文では，発見確率を最大にする繰り返し回数（最適な繰り返し回数）はO(\sqrt{N/r})であることを示している．この最適な繰り返し回数は，初期状態の場合の最適な繰り返し回数と同じオーダーである．
2 The Recursion Equations
2.1 The Generalized Algorithm
Generalizedといっても，初期状態が一様とは限らないことを除けば，Grover's algorithmとすることは同じ．発見確率が最大になるsteps数Tが知りたい．この節に，inversion about average の操作をするための行列が書かれている．
2.2 Dynamics
Dyanamicsは日本語訳は力学でいいのか．検索すると，そのままダイナミクスと書いてあるサイトが多い．
この節では，マークされた状態（marked state）とマークされていない状態（unmarked state）の振幅のtime evolusionの漸化式が与えらえている．この式の特徴は，全体のdynamicsがmarked stateの振幅の平均とunmarked stateの平均で全体の時間発展が書けていること．個々の状態の振幅の漸化式は，Theorem 1で示されている．inversion about averageの操作のために，全振幅の重み付き平均が振幅変化に影響を与えている．
Theorem 1の式の証明は難しくない．C(t)を定義した理由がわかる．振幅の漸化式がわかったので，この漸化式から一般式を求めるのが3章．
3 Solution of the Recursion Equations
Theorem 1の漸化式から一般式を求める方法が書いてある．Theorem 1の初期状態は任意だが，初期状態が一様のとき，つまり通常のGrover's algorithmの場合の一般式を求めることについて，文献[BBHT96]に以下の言及がある．
This can be obtained by standard techniques -- and a little sweat -- from recurence.
この章の求め方を見たとき，little sweat と言った理由がわかった．式を追うときは書かれていない途中の式を書きながらでないとできなかったし，自力で見つけようとすると，できたかどうか．
式(10)(11)を式(4)(5)に代入すれば，個々のmarked stateの振幅の漸化式，個々のunmarked stateの漸化式が得られる．個々の振幅については，まだ漸化式なので，さらに一般式を求める必要がある．これをするのが，4.2章．
4 Analysis
4.1 Phase Difference
marked stateの平均とunmarked stateの平均をsin, cosで表すと，ちょうど\pi/2だけずれているので，marked stateの平均が最大のとき，unmarked sateの平均が最小になる，と書いてある．これは正確には，"marked stateの振幅の2乗"ではないか．
when the averate marked amplitude is maximal, the average unmarked amplitude is minimal, and vice versa.
4.2 Constant Variance
式(18), (19)が言っていることは，marked stateの振幅は，Grover iterationをするとき，1回あたりの増分は各state毎の定数であること．正確には，marked stateの平均の振幅とそのmarked sateの振幅の差はGrover iterationの回数によらず一定であることを示している．
marked stateの平均振幅の時間変化が分かれば，marked stateの個々の振幅の増分は初期状態から計算できるので，平均振幅の時間変化を求めることが重要．平均振幅は，式(12)(13)の閉じた式から求められる．式(12)(13)は三角関数の式なので，時間によって値が増減する．つまり，平均振幅の値は，時間によって増減する．その平均振幅からの差分は，個々のstateによって異なるが，その差分は時間変化しない，固定値である．
個々のstateの振幅を表す式(18)(19)に式(12)(13)を代入すれば，発見確率が最大になる回数がわかる．その回数を具体的に求めているのが，4.3章．今は，marked stateが一つでも見つけられればよい，という問題を考えている点に注意．全部見つけるという問題ではない．
4.3 Maximal Probability of SUccess and Optimal Number of Iterations
成功確率の最大値は式(21)で与えられている．初期状態のumarked sateの振幅の分散の分だけ確率が低くなる．初期状態のunmarked stateの分散が0の一様分布のときが成功確率が最大の1になる．
成功確率が最大になるときの繰り返し回数Tが式(24)で与えられていて，arctan, arccosが出てきているが，式(23)を変形しただけの式．この式(24)は実数の値をとるが，Tは繰り返し回数なので，式(24)のjを変化させてて，整数にできるだけ近い値が最適な繰り返し回数になる．
式(25)はj=0のときに展開して，式(24)を近似した式．第1項と第2項が主要項．初期状態の振幅に依存して，繰り返し回数が定数回だけ減る．成功確率が減った分に比べると，繰り返し回数の減った分は微々たるもの．初期状態が非一様分布の場合，繰り返し回数は定数回程度減るかもしれないが，成功確率は非一様さに応じて減っていく．初期状態が非一様になると，いいことはほとんどなくて，悪くなるばかりということか．
5 Summary and Conclusions
任意の初期状態において，Grover's algorithmの最適な繰り返し回数は，総数の平方根のオーダーである点は変わらないが，発見確率は，非一様さ，正確には，unmarked stateの振幅の分散に比例して，一様のときと比較して低くなる．初期状態は一様が最もよい．