# Intuitively, what does the quantum Fourier transform do?

I somewhat understand its practical use in phase estimation and algorithms like Shor's algorithm but is there some more intuitive way of understanding what it does?

More concretely, I'd like to know if there is there some way of thinking about how it effects the probability of the base states and similarly, is there a way of considering how it effects the probability of the outcome of measurement of each input qubit?

• Hey @dhjtricks! Welcome to the community. To clarify, are you interested in QFT or QFT inverse? Shor's and QPE both use QFT inverse, an important clarification. The exact transformation is described here: en.wikipedia.org/wiki/Quantum_Fourier_transform#Definition – C. Kang Jul 30 '20 at 17:29
• @C.Kang Thanks for the welcome! I'm interested in both actually. I've looked over the QFT wikipedia page and understand what it is. I'd just like to know if there is some intuitive way to think about it, similar to how one might think (informally) about the Hadamard gate as giving the qubit equal chance of being one basis state or the other when applied to |0> or |1>. – dhjtricks Jul 30 '20 at 18:40
• Super cool! I think the question will really depend on the style of the answerer. I think a core distinction is that quantum operations really can't be thought of having clear classical analogues - while Hadamard certainly does put $|0 \rangle$ into $|+\rangle$, the concept of the $|-\rangle$ state isn't intuitive for classical programmers. Does that make sense, or are we thinking of intuition to different backgrounds? :- ) – C. Kang Jul 30 '20 at 19:58
• @C.Kang You make a good point. I think I was being a bit too liberal with my use of the word 'intuition'. Perhaps I should clarify myself. Is there an analogue for the QFT in a similar vain to how I described the Hadamard gate? – dhjtricks Jul 30 '20 at 20:25
• @dhjtricks in regards to your "intuitive description" of the Hadamard hate, the QFT works in exactly the same way: if gives equiprobable outputs when the input is an element of the computational basis. – glS Aug 1 '20 at 10:35

Let's see what QFT does on two qubit (and then on three qubit) computational basis states and try to gain some insights. The QFT action on $$|j\rangle$$ basis state:

$$QFT |j\rangle = \frac{1}{2^{\frac{n}{2}}} \sum_{k=0}^{2^n -1} e^{2 \pi i \frac{jk}{2^n}} |k\rangle$$

where $$n$$ is the qubit number. Now suppose $$n=2$$, then:

\begin{align*} QFT |00\rangle &= QFT |0\rangle = \frac{1}{2} \sum_{k=0}^{3} e^{2 \pi i \frac{0 \cdot k}{4}} |k\rangle = \frac{1}{2}\big( |0\rangle + |1\rangle + |2\rangle + |3\rangle \big) \\ QFT |01\rangle &= QFT |1\rangle = \frac{1}{2} \sum_{k=0}^{3} e^{2 \pi i \frac{1 \cdot k}{4}} |k\rangle = \frac{1}{2}\big( |0\rangle + i |1\rangle - |2\rangle - i|3\rangle \big) \\ QFT |10\rangle &= QFT |2\rangle = \frac{1}{2} \sum_{k=0}^{3} e^{2 \pi i \frac{2 \cdot k}{4}} |k\rangle = \frac{1}{2}\big( |0\rangle - |1\rangle + |2\rangle - |3\rangle \big) \\ QFT |11\rangle &= QFT |3\rangle = \frac{1}{2} \sum_{k=0}^{3} e^{2 \pi i \frac{3 \cdot k}{4}} |k\rangle = \frac{1}{2}\big( |0\rangle - i|1\rangle - |2\rangle + i|3\rangle \big) \end{align*}

From here one can see that each $$|j \rangle$$ after QFT becomes a superposition state of all basis states with equal probabilities (in this case the probability is equal to $$\frac{1}{4}$$). And because QFT is a unitary operator, if $$\langle j | j'\rangle= 0$$ (when $$j \ne j'$$), then $$\langle j |QFT^{\dagger} QFT | j'\rangle= 0$$, so the states generated by $$QFT | j\rangle$$ are different superposition states with equal probabilities that are orthogonal to each other.

Now three qubit case. I will write down only for three cases:

\begin{align*} QFT &|000\rangle = QFT |0\rangle = \frac{1}{2^{\frac{3}{2}}} \sum_{k=0}^{7} e^{2 \pi i \frac{0 \cdot k}{2^n}} |k\rangle = \\ &=\frac{1}{2^{\frac{3}{2}}}\big( |0\rangle + |1\rangle + |2\rangle + |3\rangle + |4\rangle + |5\rangle + |6\rangle + |7\rangle\big) \\ QFT &|001\rangle = QFT |1\rangle = \frac{1}{2^{\frac{3}{2}}} \sum_{k=0}^{7} e^{2 \pi i \frac{1 \cdot k}{8}} |k\rangle = \\ &=\frac{1}{2^{\frac{3}{2}}}\big( |0\rangle + e^{i \frac{\pi}{4}}|1\rangle + e^{i \frac{\pi}{2}}|2\rangle +e^{i \frac{3 \pi}{4}} |3\rangle + e^{i \pi}|4\rangle +e^{i \frac{5\pi}{4}} |5\rangle + e^{i \frac{3\pi}{2}}|6\rangle + e^{i \frac{7 \pi}{4}}|7\rangle\big) \\ QFT &|111\rangle = QFT |7\rangle = \frac{1}{2^{\frac{3}{2}}} \sum_{k=0}^{7} e^{2 \pi i \frac{7 \cdot k}{8}} |k\rangle = \\ &=\frac{1}{2^{\frac{3}{2}}}\big( |0\rangle + e^{i \frac{7 \pi}{4}}|1\rangle + e^{i \frac{3\pi}{2}}|2\rangle +e^{i \frac{5 \pi}{4}} |3\rangle + e^{i \pi}|4\rangle +e^{i \frac{3\pi}{4}} |5\rangle + e^{i \frac{\pi}{2}}|6\rangle + e^{i \frac{ \pi}{4}}|7\rangle\big) \end{align*}

This time also $$QFT |j\rangle$$ generates superposition states with equal probabilities (note that $$| \frac{e^{i\varphi}}{2^{\frac{3}{2}}}|^2 = \frac{1}{8}$$ for any given $$\varphi$$ ) that are orthogonal to each other. The same logic works for arbitrary number of qubits $$n$$. $$H$$ can be regarded as one qubit QFT and note that $$H |j \rangle$$ ($$j = 0,1$$), in the same manner, also produces superposition states with equal probabilities that are orthogonal to each other.

If instead of computational basis $$|j \rangle$$ we apply QFT on an arbitrary superposition state $$\sum_{j = 0}^{2^n -1} a_j |j\rangle$$ things get slightly complicated:

$$QFT \sum_j a_j |j\rangle = \frac{1}{2^{\frac{n}{2}}} \sum_{l,k=0}^{2^n -1} e^{2 \pi i \frac{lk}{2^n}} | k \rangle \langle l | \sum_{j = 0}^{2^n -1} a_j |j\rangle = \frac{1}{2^{\frac{n}{2}}} \sum_{j,k=0}^{2^n -1} a_j e^{2 \pi i \frac{jk}{2^n}} | k \rangle$$

And the probability of measuring $$|k \rangle$$ is equal to:

$$p_k = \frac{1}{2^n} \left|\sum_{j = 0}^{2^n - 1} a_j e^{2 \pi i \frac{jk}{2^n}} \right|^2$$

As an example let's apply QFT on this Bell state $$| \Phi^+ \rangle = \frac{1}{\sqrt{2}} \big(|00\rangle + |11\rangle \big) = \frac{1}{\sqrt{2}} \big(|0\rangle + |3\rangle \big)$$:

$$QFT \frac{1}{\sqrt{2}} \big(|0\rangle + |3\rangle \big) = \frac{1}{2 \sqrt{2}} \big(2|0\rangle + (1 - i)|1\rangle + (1 + i)|3\rangle \big)$$

The probability of measuring $$|0\rangle$$ state is equal to $$\frac{1}{2}$$, but the probability of measuring $$|1\rangle$$ or $$|3\rangle$$ states are equal $$\frac{1}{4}$$. Also, note that the probability of measuring $$|2\rangle$$ state is zero in this case.