@article {2154, title = {Approximate Quantum Fourier Transform with O(nlog(n)) T gates}, journal = {npj Quantum Information }, volume = {6}, year = {2020}, month = {3/13/2020}, abstract = {
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.
}, doi = {https://doi.org/10.1038/s41534-020-0257-5}, url = {https://arxiv.org/abs/1803.04933}, author = {Yunseong Nam and Yuan Su and Dmitri Maslov} }