%0 Journal Article %J npj Quantum Information %D 2020 %T Approximate Quantum Fourier Transform with O(nlog(n)) T gates %A Yunseong Nam %A Yuan Su %A Dmitri Maslov %X

The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer enables the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, and phase estimation. The standard fault-tolerant implementation of an n-qubit 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 O(n log2 (n)). In this paper we show how to obtain approximate QFT with the t-count of O(n log(n)). Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

%B npj Quantum Information %V 6 %8 3/13/2020 %G eng %U https://arxiv.org/abs/1803.04933 %N 26 %R https://doi.org/10.1038/s41534-020-0257-5