折り返しの仕組み

これまでは折り返し変換をブラックボックスとして使ってきました。 折り返し変換は回路の形が決まっているので、実際に中身を知らなくてもグローヴァー探索を実装できます。

しかし一体なぜ「折り返し」と呼ばれるのか、知っていても損はありません。 ここでは、位相反転した振幅の大きさがなぜ増幅するのか、折り返し変換を幾何学的に捉えることで直感的に説明します。

初期状態

折り返し変換をかける前の状態ベクトルは、たとえば次のようになっています。 ここでは 4 つの振幅はすべて等しく確率が 25% で、1 つだけ位相が反転しています。 このとき、図のように青の円周と位相の交点の座標をそれぞれ求めておきます。

平均を求める

次に、それぞれの点の平均座標を求めます。 x 座標はそれぞれ 0 なので平均も 0 です。 y 座標は \((0.5 + 0.5 + 0.5 - 0.5) / 4 = 0.25\) となります。 求めた平均座標は赤い丸として円表示の中に描いておきます。

平均で折り返す

次に、平均座標 (赤い丸) を中心にして、それぞれの元の座標 (白い丸) と対称な点を取ります。 これが折り返しという名前の由来です。 位相が上を向いている左の 3 つの振幅は、平均からそれほど離れていないため折り返した点が近くになります。 一方で、位相が下を向いている振幅は 1 つだけ平均から離れるため、折り返した点も遠くになります。

最後に折り返しによって得られた点を元に、振幅の大きさと位相を描き直します。 ここでは左の 3 つは、振幅の大きさが 0 になります。 そして一番右の振幅は、大きさが 1 になり位相も上向きになります。

以上の手順により、2 量子ビットで 1 つだけ位相反転した状態ベクトルに折り返し変換をかけた結果は、次のようになります。 たしかに、位相反転した振幅だけ確率が 100% に増幅していることが分かります。

まとめ

折り返し変換はいわば「平均を取って折り返す」という操作です。 ひとつだけ位相が反転している振幅の座標は、平均から大きく離れます。 このため、平均を中心として折り返した後の違いが顕著になります。 この操作を適切な回数繰り返すことで、位相の違いを振幅の大きさの違いにうまく変換できます。