01345nas a2200145 4500008004100000245006600041210006200107260001400169490000600183520092300189100001801112700001301130700001901143856003701162 2020 eng d00aApproximate Quantum Fourier Transform with O(nlog(n)) T gates0 aApproximate Quantum Fourier Transform with Onlogn T gates c3/13/20200 v63 a
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.
1 aNam, Yunseong1 aSu, Yuan1 aMaslov, Dmitri uhttps://arxiv.org/abs/1803.04933