Looking at Qiskit's QFT tutorial, their implementation of QFT requires you to swap the qubits at the end (Nielsen and Chuang do this too). I'm wondering why this is the case. Can we flip the gates upside down instead of swapping the qubits at the very end? Is there something crucial that I'm missing?

Swap in QFT circuit


1 Answer 1


To understand why we need to reverse the qubit, let's take the formula given at the end of the part 4 of the tutorial you are pointing at. This formula is a rewrite of the QFT basis formula which is the transformation we're trying to achieve :

$$QFT_N|x\rangle=\frac{1}{\sqrt{N}}\left(|0\rangle+e^{\frac{2 \pi i}{2} x}|1\rangle\right) \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2^{2}} x}|1\rangle\right) \otimes \ldots \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2^{n-1}} x}|1\rangle\right) \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2^{n}} x}|1\rangle\right)$$

And the formula given at the end of the part 5, which is the state obtained after the QFT circuit :

$$\frac{1}{\sqrt{2}}\left[|0\rangle+\exp \left(\frac{2 \pi i}{2^{n}} x\right)|1\rangle\right] \otimes \frac{1}{\sqrt{2}}\left[|0\rangle+\exp \left(\frac{2 \pi i}{2^{n-1}} x\right)|1\rangle\right] \otimes \ldots \otimes \frac{1}{\sqrt{2}}\left[|0\rangle+\exp \left(\frac{2 \pi i}{2^{2}} x\right)|1\rangle\right] \otimes \frac{1}{\sqrt{2}}\left[|0\rangle+\exp \left(\frac{2 \pi i}{2^{1}} x\right)|1\rangle\right]$$

You can easily see that these two formulas are quite similar. The only difference between them is that the order of the factor is inverted. To obtain the first formula, you need to apply a set of $SWAP$ gates to put the qubits back in the good order.

This is not equivalent with flipping the whole circuit upside down. Here's why :
Let's see what append if you apply the flipped circuit:
The initial state is : $|x_1\rangle|x_2\rangle...|x_{n-1}\rangle|x_n\rangle$
You apply a $H$ gate on the last qubit and obtain the state : $$|x_1\rangle|x_2\rangle...|x_{n-1}\rangle\frac{1}{\sqrt2}(|0\rangle + e^{\frac{2i\pi}{2}x_n}|1\rangle)$$ then, you apply $UROT_2$ gate controlled by the $n-1$ qubit and obtain : $$|x_1\rangle|x_2\rangle...|x_{n-1}\rangle\frac{1}{\sqrt2}(|0\rangle + e^{\frac{2i\pi}{2^2}x_{n-1} + \frac{2i\pi}{2^1}x_n}|1\rangle)$$ and after the nth $UROT$ gate : $$|x_1\rangle|x_2\rangle...|x_{n-1}\rangle\frac{1}{\sqrt2}(|0\rangle + e^{\frac{2i\pi}{2^n}x_{1} + ... + \frac{2i\pi}{2^2}x_{n-1} + \frac{2i\pi}{2^1}x_n}|1\rangle)$$ with : $$e^{\frac{2i\pi}{2^n}x_{1} + ... + \frac{2i\pi}{2^2}x_{n-1} + \frac{2i\pi}{2^1}x_n} = \prod_{k=1}^{n}e^{2i\pi \frac{x_k}{2^{n-k}}}$$ when the phase we would like to obtain is : $$e^{\frac{2i\pi}{2^n}x_{n} + ... + \frac{2i\pi}{2^2}x_2 + \frac{2i\pi}{2^1}x_1} = \prod_{k=1}^{n}e^{2i\pi \frac{x_k}{2^{k}}} = e^{\frac{2i\pi x}{2^n}}$$

Without going any further in the circuit, we can already see that the transformation on the last qubit differs from what we would like to achieve, not only in the order of the qubits but also in the obtained phase (the important part of the $QFT$).

  • 1
    $\begingroup$ The surprising thing in part 2.1 showing the "intuition" (learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform) is that the input is conform to the qiskit bit ordering convention (least significant bit with lowest id/most significant with highest id) whereas the output seams contradictory to this convention : in the output animation I would expect the slowly rotating qubit phase to correspond to the most significant bit, the fastest to least significant (since this smallest bit is changing often). Wouldn't it be more consistent to avoid swapping ? $\endgroup$ Commented Nov 28, 2022 at 19:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.