Quantum Fourier Transform without SWAPs

Question

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?

Answer 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 to 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 work around 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 fairly straightforward to adapt this technique to Nielsen's circuit I think.

Here is 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! :)

Answer 2

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

Answer 3

$ \def\bra#1{{\langle#1|}} \def\ket#1{{|#1\rangle}} $

The mathematical notation and the respective circuits (without swaps) for little- and big-endian of the $QFT$ are shown below:

---

Little-endian:

$$QFT_N(\ket{x_1x_2\dots x_n}) = \frac{1}{\sqrt{N}}(\ket{0}+e^{2\pi i[0.x_n]}\ket{1})\otimes(\ket{0}+e^{2\pi i[0.x_{n-1}x_n]}\ket{1})\otimes\dots\otimes(\ket{0}+e^{2\pi i[0.x_1x_2\dots x_n]}\ket{1})$$

---

Big-endian:

$$QFT_N(\ket{x_n\dots x_2x_1}) = \frac{1}{\sqrt{N}}(\ket{0}+e^{2\pi i[0.x_1]}\ket{1})\otimes(\ket{0}+e^{2\pi i[0.x_2x_1]}\ket{1})\otimes\dots\otimes(\ket{0}+e^{2\pi i[0.x_n\dots x_2x_1]}\ket{1})$$

---

2. Note, that according to the mathematical expression, the qubits in the circuit are ordered the wrong way around. For little-endian, qubit $\ket{x_1} = \frac{1}{\sqrt{2}}(\ket{0}+e^{2\pi i[0.x_1\dots x_n]}\ket{1})$ and qubit $\ket{x_n} = \frac{1}{\sqrt{2}}(\ket{0}+e^{2\pi i[0.x_n]}\ket{1})$, while the first vector of the tensor product, corresponding to the first qubit, is $\frac{1}{\sqrt{2}}(\ket{0}+e^{2\pi i[0.x_n]}\ket{1})$ and the $n$-th vector, corresponding to the $n$-th qubit, is $\frac{1}{\sqrt{2}}(\ket{0}+e^{2\pi i[0.x_1\dots x_n]}\ket{1})$. That's why we need the swaps in the first place. At present (18.12.2021), the Wikipedia article mentions this:

   To obtain this state from the circuit depicted above, a swap operation of the qubits must be performed to reverse their order. At most $n/2$ swaps are required.

1. Flipping the circuit upside down (or swapping beforehand) is equivalent to inverting the endianness. This can be seen by comparing the two circuits above (I changed the ordering of the qubits on the left side instead of flipping the circuit upside down). If both circuits were the same, except for swap operations at the end, the results of the qubits $\ket{x_i}$ and $\ket{x_{n-(i-1)}}$ (where $i\in\{1,\dots,n\})$, in the respective circuits, would be the same. But, this is not the case. For example $\ket{x_n} = \frac{1}{\sqrt{2}}(\ket{0}+e^{2\pi i[0.x_n]}\ket{1})$ (little-endian) is not equal to $\ket{x_1} = \frac{1}{\sqrt{2}}(\ket{0}+e^{2\pi i[0.x_1]}\ket{1})$ (big-endian).

---

From Quirk's 8-qubit $QFT$ example I constructed interactive example circuits according to the question:

• QFT circuit
• Flipped QFT circuit

Since Quirk uses big-endian, the preceding swaps convert the state to little-endian. Removing the preceding swaps of the flipped $QFT$ circuit yields the big-endian $QFT$. Keep in mind, that the swaps after the $QFT$ are missing in these examples.