Improved Exact and Approximate Quantum Fourier Transforms from MultiplicationResearch Paper
The quantum Fourier transform (QFT) changes between the computational basis and a basis indexed by phases. Quantum algorithms use this change of basis in phase estimation, period finding, and Shor's factoring algorithm. Its circuit size therefore contributes to the cost of those algorithms. The standard exact circuit uses quadratically many gates in the…