量子フーリエ変換 (QFT)
QFT の内部
QFT の仕組みを理解する
QFT の動作を調べてみましょう。QFT を理解するには、逆 QFT 回路の動作を追ってみるのが簡単です。 逆 QFT の動作が理解できれば、単純な逆回路である QFT の動作も理解したことになります。
例として、周波数 2 のパターンを状態ベクトルに書き込む逆 QFT 回路を考えます。 これは前回に出てきた回路と同じで、次の形になります。
パターンの読み出しでは同じ状態ベクトルをもっと短い以下の回路で準備しました。 この回路が何をやっているか分析することで、逆 QFT の内部についても理解が進みます。
この回路では下から 4 ビット目にだけ
それぞれの
ここで \(\frac{π}{4}\) は周波数 2 での位相の単位を表しています。 これは、周波数 2 の波を作るには、次のように隣りあう円同士で位相を \(\frac{π}{4}\) ずらせば作ることができる、ということを表しています。
一般に周波数 \(n\) の位相回転を作るには、量子ビット数を \(N\) とすると、位相の単位は \(n \times \frac{2π}{2^N}\) となります。 そして 1 ビット目に \(1 \times n \times \frac{2π}{2^N}\), 2 ビット目に \(2 \times n \times \frac{2π}{2^N}\), 3 ビット目に \(4 \times n \times \frac{2π}{2^N}\) の位相回転... という風に 2 のべき乗で回転する回路によって、周波数 n の位相回転を作ることができます。
たとえば 4 量子ビットで周波数 3 の場合には、位相の単位は \(3 \times \frac{2π}{2^4} = \frac{6π}{16}\) です。 これによって、周波数 3 の位相回転を作る回路は次のようになります。
これをふまえて、周波数 2 の場合について逆 QFT の動作を見ていきましょう。 逆 QFT 回路の構造は、次のように 5 つのブロックに分割できます (最初の「2を入力」のブロックは除く)。
最初の
次に \(1 \times \frac{π}{4}\) のブロックを見てみましょう。
最初の
次の \(2 \times \frac{π}{4}\) のブロックも同様です。 最初の
次の \(4 \times \frac{π}{4}\) のブロックは少し事情が異なります。
入力の 3 ビット目は 1 なので、これに
最後のブロックの
しかしここでの回転は 2π であるため 0° の回転と同じであり、単純な重ね合わせと同じ効果を持ちます。
まとめ
逆 QFT の動作を追うことで、状態ベクトルに位相のパターンを書き込む方法を見てきました。
この仕組みは、入力や量子ビット数が異なってもうまく動作します。 つまり QFT と逆 QFT をブラックボックス的なサブルーチンと考え、他のいろいろな量子アルゴリズムの一部として便利に使うことができます。