



@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 = {<p>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.</p>},
	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}
}
