量子フーリエ変換 (QFT)

QFT の内部

QFT の仕組みを理解する

QFT の動作を調べてみましょう。QFT を理解するには、逆 QFT 回路の動作を追ってみるのが簡単です。 逆 QFT の動作が理解できれば、単純な逆回路である QFT の動作も理解したことになります。

例として、周波数 2 のパターンを状態ベクトルに書き込む逆 QFT 回路を考えます。 これは前回に出てきた回路と同じで、次の形になります。

パターンの読み出しでは同じ状態ベクトルをもっと短い以下の回路で準備しました。 この回路が何をやっているか分析することで、逆 QFT の内部についても理解が進みます。

この回路では下から 4 ビット目にだけ がありません。 そこで角度が \(2π\)、つまり何もしない をあえて加えると、次の同等な回路に変換できます。

それぞれの の角度には、あるパターンがあることが分かるでしょうか? 回路を次のように書き直すと、このパターンが明らかになります。 それぞれの は、各ビットを \(\frac{π}{4}\) の整数倍、位相を回転しています。 そして係数となる整数は、上位ビットになるにつれて 2 のべき乗で増えていくことも分かります。

ここで \(\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を入力」のブロックは除く)。

最初の のペア 2 つは、量子ビットを上下にひっくり返します。 ここでは最初に 2 (2 進数で 0010) を入力しているので、 はこれを上下にひっくり返して 4 (0100) に変換します。 これは次の回路と同等になります (入力の上から 3 ビット目が \(|1\rangle\) に変わっていることに注意)。

次に \(1 \times \frac{π}{4}\) のブロックを見てみましょう。

最初の で 1 ビット目が重ね合わせ状態になります。 次に \(\frac{π}{2}, \frac{π}{4}, \frac{π}{8}\) ほど位相を回転する の組が続きます。 ここで下から 3 ビット目のみが 1 なので、このうち発火する は角度が \(\frac{π}{4}\) のもののみです。 つまり、全体では 1 ビット目を等しい重ね合わせ状態にし、位相を \(\frac{π}{4}\) 回転していることが分かります。

次の \(2 \times \frac{π}{4}\) のブロックも同様です。 最初の で 2 ビット目を重ね合わせ状態にし、2 ビット目の位相を \(\frac{π}{2} (= 2 \times \frac{π}{4})\) ほど回転させます。

次の \(4 \times \frac{π}{4}\) のブロックは少し事情が異なります。

入力の 3 ビット目は 1 なので、これに を適用すると、等しい重ね合わせを作ると同時に \(|1\rangle\) の位相を π 回転させます。 これは \(4 \times \frac{π}{4}\) の回転です。 つまりここの は、重ね合わせと位相の回転を 1 つの で行っています。

最後のブロックの も重ね合わせと位相の回転を同時に行います。

しかしここでの回転は 2π であるため 0° の回転と同じであり、単純な重ね合わせと同じ効果を持ちます。

まとめ

逆 QFT の動作を追うことで、状態ベクトルに位相のパターンを書き込む方法を見てきました。 をうまく使うことで、 重ね合わせと位相の回転をコンパクトにまとめることができます。

この仕組みは、入力や量子ビット数が異なってもうまく動作します。 つまり QFT と逆 QFT をブラックボックス的なサブルーチンと考え、他のいろいろな量子アルゴリズムの一部として便利に使うことができます。