Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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?
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.
