# Nielsen and Chuang -- Chapter 5

The quantum fourier transform on an orthonormal basis $\ket{0}, \cdots ,\ket{N - 1}$ is defined to be a linear operator with the following action on the basis states,

\[\ket{j} \rightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk / N} \ket{k}\]### (5.2) Explicitly compute the Fourier transform of the $n$ qubit state $\ket{00\cdots 0}$.

$\ket{00 \cdots 0 }$ corresponds to state $\ket{0}$ in the size $N = 2^n$ computational basis. Hence, using the formula above we have

\begin{align}
\ket{0} \rightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \ket{k} \

&= \frac{\ket{0} + \ket{1} + \cdots + \ket{N-1}}{\sqrt{N}}
\end{align}

### (5.7) Additional insight into the circuit above may be obtained by showing, as you should now do, that the effect of the sequence of controlled-$U$ operations like that in the figure is to take the state $\ket{j}\ket{u}$ to $\ket{j} U^j\ket{u}$. (Note that this does not depend on $\ket{u}$ being an eigenstate of $U$.)

Consider an arbitrary $j$ in its binary representation $j_0j_1 \cdots j_{t-1}$ where $j_i \in { 0, 1}$. Hence, for each $\ket{j_i}$, the control-$U$ acts on $\ket{j_i}\ket{u}$ such that $\ket{j_i}\ket{u} \mapsto \ket{j_i}U^{j_i 2^i}\ket{u}$. Therefore, the final state is given by

\(\begin{align}\ket{j_0 } \cdots \ket{j_{t-1}}U^{j_0 2^0} \cdots U^{j_{t-1} 2^{t-1}}\ket{u} &= \ket{j} U^{j_0 2^0} \cdots U^{j_{t-1} 2^{t-1}}\ket{u}\\ &=\ket{j} U^{j_0 2^0 + j_{t-1} 2^{t-1}}\ket{u}\\ &= \ket{j} U^{j}\ket{u}\end{align}\)