2018/03/31 by Yunseong Nam, Yuan Su, Dmitri Maslov · 2 citations
Physics and Astronomy · Computer Science · #quant-ph #cs.ET
paper · pdf · doi:10.1038/s41534-020-0257-5
published as npj Quantum Information 6, 26 (2020) · 7 pages, improved gate counts
arxiv created 2019/07/18 · arxiv updated 2020/04/09
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 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.