September 26, 2022

Approximate Quantum Fourier Transform (QFT) with O(n log(n)) T gates

The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few.

The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of 𝑂(𝑛log2(𝑛)).

Researchers from IonQ, IBM and University of Maryland have showed how to obtain approximate QFT with the T-count of 𝑂(𝑛log(𝑛)). For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Their approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. They have reported asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

Read more.