# Solution to Nielsen & Chuang Exercise 5.3 (FFT)

Can somebody help me with the solution of Nielsen Chuang, where we are supposed to derive the FFT from the equation (5.4):

$$|j_1,\ldots,j_n\rangle\rightarrow\frac{\big(|0\rangle+e^{2\pi i 0.j_n}|1\rangle\big)\big(|0\rangle+e^{2\pi i 0.j_{n-1}j_n}|1\rangle\big)\cdots \big(|0\rangle+e^{2\pi i 0.j_1j_2\cdots j_n}|1\rangle\big)}{2^{n/2}}.\tag{5.4}$$

I know that I have to somehow split it into even and odd parts to get the FFT, but I don't see how exactly I am supposed to do that.

Thanks for the help in advance.

• please have a look at quantumcomputing.meta.stackexchange.com/questions/49/… to see how to format math on the site
– glS
Jan 22 at 14:51
• isn't the explanation given explicitly in the text? Cna you be more specific on what you find unclear about it?
– glS
Jan 23 at 13:43

It seems like a homework question so I will not give full details.

First, the question asks to show that a straightforward application of DFT takes $$\Theta(2^{2n})$$ operations on an input with $$2^n$$ components. This is quite easy to see if we look at the $$2^n \times 2^n = 2^{2n}$$ matrix of DFT: $$W = \frac{1}{\sqrt{2^n}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{2^n-1} \\ 1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(2^n-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(2^n-1)}\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega^{2^n-1}&\omega^{2(2^n-1)}&\omega^{3(2^n-1)}&\cdots&\omega^{(2^n-1)(2^n-1)} \end{bmatrix}.$$ If we multiply $$W$$ with a vector and count the operations we get the result.

Now, how can we cut down the operation count using equation (5.4)?

Equation (5.4) allows you to take advantage of the fact that the Fourier transformed $$|j_1, j_2, \ldots, j_n\rangle$$ is made out of $$n$$ tensored $$2\times 1$$ vectors. So, we process each $$2\times 1$$ vector independently by performing the following $$n$$ mappings:

\begin{align} \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) &\rightarrow \frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i 0.j_n}|1\rangle),\\ \vdots\\ \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) &\rightarrow \frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i 0.j_1 \ldots j_n}|1\rangle). \end{align} Each mapping takes a constant number of operations in $$n$$ as it is simply multiplying a $$2 \times 1$$ vector by a $$2\times 2$$ phase matrix. I believe in the book the matrix is as follows: $$R_k = \begin{pmatrix} 1 && 0\\ 0 && e^{2 \pi i /2^k} \end{pmatrix}.$$ Hence, we perform $$n$$ matrix-vector multiplication to process a single $$|j_1\ldots j_n\rangle$$.

We know that an arbitrary vector $$|\psi\rangle$$ on $$n$$ qubits can be written as a linear combination of $$2^n$$ binary kets $$|j_1, j_2, \ldots, j_n\rangle$$. For example, for $$n=2$$, an arbitrary state can be written as a linear combination of $$2^2$$ binary kets like so $$|\psi\rangle = a |00\rangle + b|01\rangle +c|10\rangle+d|11\rangle.$$

Therefore, to transform $$|\psi\rangle$$ on $$n$$ qubits, we need to process $$2^n$$ binary vectors $$|j_1, \ldots j_n\rangle$$ by performing $$n$$ mappings described above. Since each such binary vector requires $$n$$ matrix-vector multiplications, and there are $$2^n$$ of them, it takes $$\Theta(n 2^n)$$ operations.