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


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 \log^2(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.
Submitted 13 Mar 2018 to Quantum Physics [quant-ph]
Published 14 Mar 2018
Subjects: quant-ph cs.ET
Author comments: 6 pages