I am reading about the quantum Fourier transform (QFT) in the qiskit textbook, but got stuck at the last part of it which shows a decomposed version of the 4 qubit QFT circuit.

enter image description here

It seems that the decomposition is a bit different than the QFT definition, in that the swap gates are placed differently. I guess some amount of simple optimizations for swap gates has been performed there in the decomposed version, but I can't figure out exactly what has happened. To me, the decomposition should look something like the following.

enter image description here

Can someone please explain?

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Endianness $\endgroup$ Commented Sep 27, 2023 at 14:00
  • $\begingroup$ On which resource do you base your decomposition on? In the QFT, the only SWAP gates are supposed to happen at the end of the circuit, but yours has some in the middle of it $\endgroup$
    – Tristan Nemoz
    Commented Sep 28, 2023 at 12:55
  • $\begingroup$ @MarkSpinelli I am following the little endian way of enumerating the qubits as the qiskit does. $\endgroup$
    – pilsungk
    Commented Oct 3, 2023 at 4:25
  • $\begingroup$ @TristanNemoz The decomposition is based on the recursive implementation as described in the qiskit textbook, where swap gates are used at every recursive step. By the way, I recently figured out the qiskit decomposition of QFT4 is equivalent to the recursive definition -- qiskit is doing a little bit of optimization to reduce the swap gates in the middle. $\endgroup$
    – pilsungk
    Commented Oct 3, 2023 at 4:39

1 Answer 1


In Qiskit textbook[1], qft function is defined as follows:

def qft(circuit, n):
    """QFT on the first n qubits in circuit"""
    qft_rotations(circuit, n)
    swap_registers(circuit, n)
    return circuit

So, QFT circuit is created by calling two functions, qft_rotations and swap_registers. And while qft_rotations function is recursive, swap_registers is not. Which means SWAP gates will be added to the circuit only once.

This is the circuit described in most introductory texts to quantum computation.

In "Phase estimation and factoring"[2] tutorial, another quantum Fourier transform circuit is described. This other circuit, inspired by fast Fourier transform algorithm, is constructed recursively. You can find the details in this paper

Due to its recursive nature, a layer of SWAP gates is added to permute the order of the qubits after each step. However, these SWAP gates can be pushed to the end of the circuit as stated clearly in the tutorial:

We don't actually need as many swap gates as the method describes — if we rearrange the gates just a bit, we can push all of the swap gates out to the right [...]

  • $\begingroup$ The recursive circuit implementation of QFT I originally asked about is described here. The four steps of implementation is, 1. Apply the 2^(m-1) dim QFT to the leftmost qubits (little endian), 2. Inject phases for each standard basis state of the (m-1) qubits, 3. Perform a Hadamard gate on the rightmost qubit, 4. Shift the qubits so that the LSB becomes the MSB. The QFT5 implementation using this definition shows here $\endgroup$
    – pilsungk
    Commented Oct 3, 2023 at 6:38
  • $\begingroup$ Thanks for the detailed answer. My question was about the second implementation in your description, and the confusing part was about the rearranging the gates to remove the swap gates in the middle, as drawn by qiskit's decompose() method. I somehow figured out how that happened and I am clear now. Thanks! $\endgroup$
    – pilsungk
    Commented Oct 3, 2023 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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