Approximate quantum Fourier transform with O(n log(n)) T gates
Open Access
- 13 March 2020
- journal article
- research article
- Published by Springer Nature in npj Quantum Information
- Vol. 6 (1) , 1-6
Abstract
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\,{\mathrm{log}}^{2}\,(n))$$ . In this paper, we show how to obtain approximate QFT with the T-count of $$O(n\,{\mathrm{log}}\,(n))$$ . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. 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.
Keywords
All Related Versions
Funding Information
- United States Department of Defense | United States Army | U.S. Army Research, Development and Engineering Command | Army Research Office (W911NF-16-1-0349)
This publication has 30 references indexed in Scilit:
- Quantum arithmetic with the quantum Fourier transformQuantum Information Processing, 2017
- Quantum cryptographic algorithm for color images using quantum Fourier transform and double random-phase encodingInformation Sciences, 2014
- Simulating Chemistry Using Quantum ComputersAnnual Review of Physical Chemistry, 2011
- Quantum algorithm for molecular properties and geometry optimizationThe Journal of Chemical Physics, 2009
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Approximating fractional time quantum evolutionJournal of Physics A: Mathematical and Theoretical, 2009
- QUANTUM SOFTWARE REUSABILITYInternational Journal of Foundations of Computer Science, 2003
- Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and EigenvectorsPhysical Review Letters, 1999
- Quantum Computers Can Search Rapidly by Using Almost Any TransformationPhysical Review Letters, 1998
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997