グロヴァー反復

前回学んだ折り返し変換を 4 量子ビット回路で行うと、答の \(|1111\rangle\) は確率が約 47.3% に上昇しましたが、さらに上昇させることはできるでしょうか? 答でない \(|0000\rangle\) などの確率はそれぞれ約 3.5% 残っていますから、これらの分を \(|1111\rangle\) の確率にさらに上積みできそうです。

実際に、振幅増幅を繰り返すことで確率をさらに上昇させることができます。 これをグローヴァー反復と呼びます。 ためしに 2 回ほど反復してみると、以下のように \(|1111\rangle\) の確率は約 90.9% まで上昇します。 このとき、\(|0000\rangle\) など他の確率は 0.6% まで減衰しています。

反復回数に限界はあるのでしょうか？ 同様に 3 回、4 回繰り返した結果は次のようになります。

実行結果を見ると、反復 3 回で \(|1111\rangle\) の確率はさらに上昇し約 96.1% まで上がります。 しかし 4 回目の反復で確率は 58.2% まで低下します。 さらに反復を続けると 6 回までは確率が下降し続けますが、それを越えるとまた上昇しはじめ 9 回目で 99.9% の確率を得ます。 そしてまた下降し、というふうに確率の上昇下降は振動になっています。

このように、グローヴァー反復はほどほどで止めないと、かえって確率を下げてしまいます。 確率の上昇下降振動のうち、最初に確率が最大になる最小の反復回数は、\(n\) を量子ビット数として一般に次の式で求めることができます。

\(N_{iter} = \lfloor\frac{π}{4}\sqrt{2^n}\rfloor\)

たとえば量子ビット数 \(n = 4\) のとき反復回数 3 で \(|1111\rangle\) の確率は約 96.1% でしたが、この反復回数 3 は \(N_{iter}\) の式から計算できます。

\[ N_{iter} = \lfloor\frac{π}{4}\sqrt{2^4}\rfloor \\ = \lfloor\frac{π}{4} \times 4 \rfloor \\ = \lfloor π \rfloor \\ = 3 \]

グローヴァー探索の計算量

ふつうの探索に比べて、グローヴァー探索がどのくらい効率的か見積もってみましょう。

ふつうの探索 (線形探索) では、要素の数が n 個あった場合に目的の要素をみつけるには最悪 \(n\) 回の繰り返しが必要です。 よって、ふつうの探索の計算量は \(O(n)\) であると言えます。

グローヴァー探索では、必要な反復回数は \(q\) を量子ビット数とすると \(\lfloor\frac{π}{4}\sqrt{2^q}\rfloor\) でした。 ここで要素数を \(n\) とすると、\(q\) 量子で表せる要素数は \(2^q\) なので、要素数 \(n\) に対して必要な反復回数は \(\lfloor\frac{π}{4}\sqrt{n}\rfloor\) となります。 計算量を見積もる上で不要な係数 \(\frac{π}{4}\) などを除くと、グローヴァー探索の計算量は \(O(\sqrt{n})\) となり、ふつうの探索の計算量 \(O(n)\) に比べて二次の加速であると言えます。

この差は \(n\) が大きいほど如実に現れます。 はじめにで見たように、2,500 万件が掲載された電話帳から特定の電話番号をみつけるには、最悪で 2,500 万件すべてに目を通す必要があります。 しかしグローヴァー探索を使えば、たった \(\sqrt{2,500万} = 5,000\) 回の繰り返しで目的の番号を見つけられます。