top of page

Quantum Fourier Transform (QFT)

Testing the performance of Ava on a central subroutine in quantum computing.


Not all quantum circuits are difficult to simulate. The quantum Fourier transform is one such 'easy' circuit, and in this post we benchmark the performance of Ava on the quantum Fourier transform for up to 2000 qubits.

The quantum Fourier transform (QFT) is an indispensable building block of many quantum algorithms. It can be used to perform basic arithmetic operations on a quantum computer, and forms the basis for quantum phase estimation and Shor's algorithm for integer factorization. For instance, applying Shor’s algorithm to factor an m-bit integer using this low-qubit implementation requires the application of around 16m^2 + 8m QFTs and inverse QFTs, meaning that factoring a 2048-bit integer would already require more than 67 million QFT circuits to be implemented.

The n-qubit QFT requires O(n^2) 1- and 2-qubit gates to be implemented exactly, but an approximate version can be obtained which only requires O(n log n) gates. This approximate version introduces some error, but will be correct with constant probability. We use this approximate version in our benchmarks, and discuss it in more detail later.

Emulating the QFT

It is well known that the quantum Fourier transform does not generate any significant entanglement, a point that is made clear by considering its sequential or ‘dynamic’ implementation. For a tensor network, simulating its application to a low entanglement state should therefore be somewhat straightforward, so long as one can properly exploit this fact (e.g. see here). In the graph below we demonstrate the performance of Ava for the task of simulating the approximate QFT applied to computational basis states on up to 2000 qubits. We found that, with default settings (and no customization of the code), Ava could automatically leverage the low-entanglement properties of the QFT to efficiently simulate circuits with very large numbers of qubits. The only setting that needed to be chosen for Ava was the bond dimension (D) – we found that a choice of D = 32 was sufficient for all qubit numbers in order to achieve an emulation fidelity of 1.

One nice feature of this benchmark (of QFT applied to basis states) is that it is easy to verify that the emulation worked correctly. Indeed, one can perform a test in the following way:

  1. Initialise the qubits in the all-zeros state.

  2. Apply a Hadamard gate to all qubits to change to the Fourier basis.

  3. Choose a random integer x, and perform addition by x in the Fourier basis via a series of single-qubit phase gates.

  4. Apply the inverse quantum Fourier transform.

  5. Measure all qubits.

The corresponding circuit is shown below, where the Rz gates will have rotation angles depending on the values of the bits of the integer x.

If the circuit runs correctly, the measurement outcome will agree with probability 1 with the computational basis state x.*

The runtimes that we report above correspond to running this circuit (which is strictly harder, albeit negligibly, than just running a QFT circuit). By running that circuit we could verify that the emulation was indeed achieving fidelity 1, and we found that, as expected, the samples returned from the emulation corresponded to our randomly chosen x's with probabilities very close to 1.

Using emulation as a circuit design tool: a toy example.

The fact that the QFT circuit is easy to emulate (given an unentangled input state) does not mean that such emulations are not useful. As we mentioned above, the QFT can be implemented approximately, which is achieved by omitting gates from the circuit that implement (controlled) rotations by very small angles - the intuition being that, since they are very small, they don't significantly affect the output. The level of approximation can be controlled by varying the threshold below which rotation gates are omitted. There are theoretical bounds on the number of gates that must be kept in order to ensure good success probability. Precisely, to achieve a constant success probability of at least 4/π^2 - 1/16 ~= 0.343 with an n-qubit QFT, it is sufficient to keep at least the (log n + 2) largest controlled rotations. However, these theoretical bounds can sometimes be a little pessimistic, and the approximate QFT might succeed with high probability even below this threshold, depending on the input state.

This is an important consideration for those looking to implement algorithms such as Shor's factoring algorithm. With so many QFTs, a slight reduction in depth of each QFT circuit could lead to a large reduction in depth in the overall circuit. Recall that 67 million QFT circuits would be required to factor a 2048-bit integer (assuming a particular implementation), meaning that any saving in depth would be amplified millions of times.

Using Ava, we repeated our benchmark (adding by a randomly chosen integer in the Fourier basis) on 1000 qubits for approximate QFTs with different degrees of approximation. The probability of the circuit giving the correct output as a function of approximation degree is shown in the graph below.

Effect of approximation on QFT
Effect of approximation degree on QFT depth and success probability, applied to product states. An approximation degree of d yields a QFT circuit that keeps only the d largest controlled rotation gates. The dotted green line marks the theoretical lower bound on the approximation degree required to give a constant success probability.

We find that the probability of success (measuring the correct integer at the end of the circuit) already becomes very close to 1 before the theoretical lower bound even takes effect. The success probability already beats the lower bound of ~0.343 at a circuit depth of 6,981, almost 6,000 fewer circuit layers than the theoretical minimum of 12,924. With only 9,957 layers, the circuit already achieves a success probability of 0.9944.

Using such insights, one might be able to use an approximate QFT of significantly lower depth than would otherwise be implied by theory, saving on circuit depth for the entire algorithm.


* When using the approximate (inverse) QFT, the measurement outcome will correspond to x with constant probability <= 1.


Commenting has been turned off.
bottom of page