TY - JOUR T1 - Approximate Quantum Fourier Transform with O(nlog(n)) T gates JF - npj Quantum Information Y1 - 2020 A1 - Yunseong Nam A1 - Yuan Su A1 - Dmitri Maslov AB -

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.

VL - 6 UR - https://arxiv.org/abs/1803.04933 CP - 26 U5 - https://doi.org/10.1038/s41534-020-0257-5 ER -