2
$\begingroup$

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

New contributor
Freeman Cheng is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
0

1 Answer 1

2
$\begingroup$

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$).

$\endgroup$

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