量子フーリエ変換 (QFT)

パターンの読み出し

状態ベクトルから周波数を取り出す

振幅増幅は位相に埋め込まれた情報を取り出すためのサブルーチンの 1 つでした。 位相の差を振幅の大きさに変換することで、位相で「マーク」を付けた値を取り出すことができます。

今回紹介する量子フーリエ変換 (QFT) は、状態ベクトルに埋め込まれたパターン情報を取り出すためのサブルーチンです。 パターンとはどのようなもので、それが何の役に立つかを見ていきましょう。

パターンの例

以下に 4 量子ビットの状態ベクトルがあります。 これにはあるパターンが隠されているのですが、みなさんには分かりますか?

ここに見られるパターンは、回転の繰り返しです。 左の円 \(|0\rangle\) から順に位相が 45° ずつ回転していき、\(|15\rangle\) までで位相が 2 回転しています。 つまりここに含まれているパターン情報は、回転を 2 回繰り返しているというものです。

パターンの取り出し

このパターン情報は、今まで見てきた方法ではうまく取り出すことができません。 たとえば測定を行った場合、それぞれの確率は等しく 6.25% なので、0 から 15 までのランダムな数が出てくるだけです。 また振幅増幅を使っても、それぞれの位相差は均等であるため、確率の差に変換することはできません。

繰り返しが 2 回であるというパターン情報は、量子フーリエ変換 (QFT) によって取り出すことができます。 先ほどの状態ベクトルを入力として QFT を適用すると、繰り返しの数 = 2 が次のように \(|2\rangle\) の確率 100% に反映されます。 そして 4 量子ビットすべてを測定することによって、2 を取り出すことができます。

QFT

QFT はフーリエ変換と呼ばれる幅広く使われるデータ処理ルーチンの量子版です。 フーリエ変換は入力に含まれる繰り返し (音の波形などの信号を入力とするとき、これを周波数と呼びます) を調べることができます。 QFT は状態ベクトル中に位相の回転としてエンコードされた周波数をフーリエ変換によって取り出すことができます。

QFT 回路

QFT を使って周波数を取り出す回路は次のようになります。 最初のブロックでは によって等しい重ね合わせを作り、続く 3 つの によって位相の回転を 2 回繰り返す入力を作りますなぜこの回路が周波数 2 の位相回転を作ることができるかは、QFT の内部で見ていきます。。 次のブロックでは QFT によって周波数を確率に変換し、最終的に \(|2\rangle\) が 100% の状態を作ることができます。

当面はこの QFT 回路をブラックボックスとしてこのまま使っていきます。 というのも、QFT の回路にはカスタマイズできる要素はなく、いつでもパターンに沿った同じ形になるためです。 量子ビット数が変わっても、 をこのパターンでならべ、最後に全ビットを で入れ替えたものが QFT の定型です。