quantum fourier transform

\[ \ket{j_1\cdots j_n} \rightarrow \frac{1}{2^{n/2}}\sum_{k=0}^{2^n-1} e^{2\pi i jk/ 2^n}\ket{k} \]

There is another way to write this formula: \[ \ket{j_1\cdots j_n} \rightarrow \frac{1}{2^{n/2}} (\ket{0} + e^{2\pi i 0.j_n} \ket{1})) (\ket{0} + e^{2\pi i 0.j_{n-1}j_n}\ket{1}) \cdots (\ket{0} + e^{2\pi 0.j_1j_2\cdots j_n} \ket{1}) \]

where \(0.j_1 j_2 \cdots j_n = \frac{1}{2} j_1 + \frac{1}{2^2} j_2 + \cdots + \frac{1}{2^n}j_n\) Let's ignore the normalizing constant for now. To see why these two formulas are equivalent, first consider the coefficient \(\ket{0\cdots 0}\). The first formula says that this should be \(1\). In the second formula, imagine selecting \(\ket{0}\) from each element of the product. Indeed we see that the coefficient is \(1\).

Now, consider the coefficient of \(\ket{0\cdots 01}\). The first formula says this should be \(e^{2 \pi i j\cdot 1/2^n}\). In the second formula, imagine selecting \(\ket{0}\) from all elements in the product except the last one. We see that selecting \(\ket{1}\) from the last term gives us a coefficient of \(e^{2 \pi i/2^n}\) just as we wanted.

Now, consider the coefficient of \(\ket{0\cdots 0 1 0}\). The first formula says this should be \(e^{2 \pi i j \cdot 2/2^n}\). This is the coefficient from above, but the term in the exponent is multiplied by 2. In the second formula, how do we multiply by 2? We shift all the bits over to the left by 1. What happens to the leftmost bit? It becomes \(1\). And all integer multiples of \(e^{2\pi}\) have no effect on the coefficient (multiplying by 1).

Now, for any arbitrary string, we see that \(k_i\) tells us what power of \(2\) to multiply \(j\) by.

A circuit can be constructed using the factored form and the matrices \(R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2 \pi i/ 2^l} \end{pmatrix}\) which controls how much the exponent should be divided by. See Nielsen and Chuang for the circuit.

\[ \ket{j} \rightarrow \sum_{k=0}^{N} e^{-2\pi i jk}\ket{k} \]

Let \(\omega = e^{2\pi i/N}\). \[M_{FT} = \begin{pmatrix} 1 & 1 & 1 & \cdots 1 \\ 1 & \omega & \omega^2 & \cdots \omega^{n-1}\\ & & & \vdots\\ 1 & \omega^{n-1} & \omega^{n-2} & \cdots \omega \end{pmatrix}\]