Approximate quantum Fourier transform with O(n log(n)) T gates

Abstract

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))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> <mml:mspace/> <mml:msup> <mml:mrow> <mml:mi>log</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mspace/> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . In this paper, we show how to obtain approximate QFT with the T-count of $$O(n\,{\mathrm{log}}\,(n))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> <mml:mspace/> <mml:mi>log</mml:mi> <mml:mspace/> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . 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.