# Quantum Fourier Transform without SWAPs

The Quantum Fourier Transform from Nielsen and Chuang chapter 5 is pictured here: 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?

• You could express the swap with controlled-rotations and Hadamards ... Jun 10 '19 at 21:23
• Do you know how that compares in gate depth assuming the circuit compiles each SWAP to three CNOTs? Jun 10 '19 at 21:37
• take a look this video youtube.com/watch?v=uuBgK44JrnA&t=2s
– 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⟩)$$

If you are using the QFT inside a bigger circuit you really can't avoid the swaps in the QFT and/or the invQFT the reason being that the value of qubit x1 dictates the symmetry of the phases in your entire superposition. Pay attention at how the phases look like in the following images:  I think your intuition in question 1 is correct but it will only work in isolation because you are then literally swapping the wires. If you need the outcome of the QFT to be used as input for something else in the circuit you'll have to use swaps at some point.

There is a way you can workaround this if you separate your input and output registers but this means you need twice as many qubits :) Then you can do something like: Quirk link so you can play with it yourself.

Note: some people mix up the invQFT with the QFT and so I myself I'm a bit lost but it should be failry straight forward to adapt this technique to Nielsen's circuit I think.

Here a video where you can see my mental process and how I got to this idea while exploring the QFT myself: https://youtu.be/HlMuFqZ9cSE?t=1158 (minute 19:18)

I hope this was helpful! :)