複数の位相反転

反転した位相が複数ある場合のグローヴァー探索はどうなるでしょうか? 今までは答が 1 つ、つまり反転した位相が 1 つの場合を見てきました。 しかしグローヴァー探索の使い途の一つである充足可能性問題では、条件を満たす答が 2 つ以上になる場合もあります。 そこで試しに、以下のように \(|0111\rangle\) と \(|1111\rangle\) の 2 つを反転させ、折り返し変換を 1 回適用した結果を見てみます。

実行すると、反転した位相が複数ある場合でもグローヴァー探索はうまく動作することが分かります。 折り返し変換を 1 回実行すると、\(|0111\rangle\) と \(|1111\rangle\) の確率が約 39% まで増幅され、それ以外は 約 1.6% まで減衰します。 このように、答が複数ある場合でも振幅増幅 (グローヴァー反復) 回路の形は変わらず、位相反転が 1 個の場合とまったく同様に実行できます。

位相反転が複数ある場合の最適な反復回数

\(n\) を量子ビット数、位相反転の数を \(m\) とすると、位相反転が複数ある場合の最適な反復回数 \(N_{iter}\) は一般に次の式で求めることができます。

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

たとえば先ほどの例では量子ビット数 \(n = 4\), 位相反転の数 \(m = 2\) なので、最適な反復回数 \(N_{iter}\) は次のように 2 となります。

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

確認のために、3 回まで反復した結果を以下の回路で確認してみましょう。 反復を 2 回行ったあとの \(|0111\rangle\) と \(|1111\rangle\) の確率は 1 回目の反復後の確率 約 39% よりも上昇し、約 47% となります。 そして、\(N_{iter} = 2\) なので、これ以上の反復は確率を減衰させることが予想できます。 実際に、さらに 3 回目の反復を行うと確率は 16.5% まで減衰します。