計算はさぼってそのまま書き出すとして、n 量子ビットでの量子 Fourier 変換は$$ | \tilde{k} \rangle = U_{QFT} \ket{k} = \frac{1}{\sqrt{N}} (\ket{0} + e^{2 \pi i k \frac{1}{2^1}} \ket{1}) \otimes (\ket{0} + e^{2 \pi i k \frac{1}{2^2}} \ket{1}) …

離散 Fourier 変換について確認してみたい。簡単のため長さ 3 の複素数列 $\{x_0, x_1, x_2\}$ を考える。$$ \begin{align*} y_m = \sum_{k=0}^2 x_k e^{-2 \pi i \frac{mk}{3}},\ 0 \leq m \leq 2 \tag{1} \end{align*} $$と置く。次に $\{y_0, y_1, y_2\}$…

通常の Fourier 変換は\begin{align*} \hat{f}(y) = \int f(x) e^{2\pi i xy} dy \end{align*}と書けるのであった。ここでは書籍との整合性のために、指数部の $-1$ を消している。これを元に、離散 Fourier 変換*1を書くと\begin{align*} y_j = \frac{1}{\s…

Simon のアルゴリズムの確認の最後として 1-to-1 の場合を見る。書籍のコードでは 1-to-1 の条件なら何でも良いということでランダム気味な回路が作られる。ある時に作られた回路を見る:この時に 1 つ目のレジスタを測定するとというようにすべての量子状態…

書籍のコードと同様に textbook のコードでも $U_f: \ket{x}\ket{0} \to \ket{x} \ket{f_s(x)}$ と 2-to-1 の時に $f_s(s^*) = f_s(0)$ であることを確認する。オラクルの問い合わせ関数だけの回路を通すと 2 つ目のレジスタから $\ket{f_s(x)}$ が観測され…