Bit-Reversal and SWAPs

The rotation stage of the QFT circuit — Hadamards plus controlled-phase gates — produces the correct Fourier amplitudes, but it places them in bit-reversed order. The final step of a standard QFT circuit corrects that order with a layer of SWAP gates.

Why the outputs are reversed

Recall the $n$ -qubit QFT definition for an input $|j\rangle$ :

\mathrm{QFT}_n|j\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n - 1} e^{2\pi i \, jk / 2^n} |k\rangle.

The rotation circuit builds the output qubit by qubit, starting from the most-significant qubit. The first qubit processed ( $q_0$ , the most significant) ends up encoding the most-significant bit of the output frequency index $k$ . The last qubit processed ( $q_{n-1}$ , least significant) encodes the least-significant bit of $k$ . In short, the rotation stage delivers the frequency index in reversed bit order.

For $n = 3$ the mapping is:

q_0 \to k_2, \quad q_1 \to k_1, \quad q_2 \to k_0

where $k = 4k_2 + 2k_1 + k_0$ in standard binary. To get the natural order ( $q_0 \to k_0,\ q_1 \to k_1,\ q_2 \to k_2$ ) we swap $q_0$ and $q_2$ .

The SWAP correction

For $n$ qubits the correction requires $\lfloor n/2 \rfloor$ SWAPs: swap qubit $0$ with qubit $n-1$ , qubit $1$ with qubit $n-2$ , and so on, stopping at the middle.

| $n$ | SWAPs needed | |-----|-------------| | 2 | 1 (swap qubits 0 and 1) | | 3 | 1 (swap qubits 0 and 2; qubit 1 stays) | | 4 | 2 (swap 0,3 and swap 1,2) |

Each SWAP costs three CNOT gates in hardware, so practitioners sometimes fold the reversal into downstream circuits to avoid paying the cost explicitly. Textbook presentations always include the SWAPs so the QFT matrix matches the classical DFT matrix exactly.

Full 3-qubit QFT

Combining the rotation stage and the SWAP correction gives the complete circuit:

$H(q_0)$ , $CP(\pi/2, q_0, q_1)$ , $CP(\pi/4, q_0, q_2)$
$H(q_1)$ , $CP(\pi/2, q_1, q_2)$
$H(q_2)$
$\mathrm{SWAP}(q_0, q_2)$

This 7-gate sequence implements the exact $8 \times 8$ QFT unitary.

Try it

The starter code contains the full rotation stage. Add the missing SWAP to put the output in natural bit order. The grader checks the full unitary matrix, so leaving the SWAP out will produce the bit-reversed variant and fail.

Run your code to see the quantum state.