The Quantum Fourier Transform from Nielsen and Chuang chapter 5 is pictured here: Quantum Fourier Transform

In the textbook the author refers to "swap gates at the end of the circuit which reverse the order of the qubits".

My questions are:

  1. Is it possible to transform the circuit shown in some way to avoid the need for any SWAP gates while still using little-endian conventions. Naively, I might think I could "flip the circuit upside down" so that the first operation is H(n), then R2 on qubit n controlled by qubit (n-1), and so on...

  2. The Wikipedia page on QFTs makes no reference to reordering or SWAP gates - does this imply a different bitstring convention between the sources, or an error in one of the sources?

  • 3
    $\begingroup$ You could express the swap with controlled-rotations and Hadamards ... $\endgroup$ – Norbert Schuch Jun 10 '19 at 21:23
  • $\begingroup$ Do you know how that compares in gate depth assuming the circuit compiles each SWAP to three CNOTs? $\endgroup$ – forky40 Jun 10 '19 at 21:37
  • $\begingroup$ take a look this video youtube.com/watch?v=uuBgK44JrnA&t=2s $\endgroup$ – Aman Jul 22 '19 at 11:43

On question 2: the Wikipedia page should have included the SWAP gates as the last step. This is corroborated by the following statement (a few lines) under your picture on the Wikipedia page:

With this notation, the action of the quantum Fourier transform can be expressed in a compact manner:$$QFT|x_1x_2\dots x_n⟩=\frac{1}{\sqrt{N}}(|0⟩+e^{2\pi i[0.x_n]}|1⟩)\otimes(|0⟩+e^{2\pi i[0.x_{n-1}x_n]}|1⟩)\otimes\dots\otimes(|0⟩+e^{2\pi i[0.x_1x_2\dots x_n]}|1⟩) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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