A Faster Quantum Fourier Transform Algorithm
2025-01-27
Ronit Shah presents an improved algorithm for the Quantum Fourier Transform (QFT). Traditionally, approximate QFT requires Θ(n log n) gates, and exact QFT requires Θ(n²) gates. The new algorithm, leveraging a novel recursive partitioning of qubits, reduces the cost of approximate QFT to Θ(n(log log n)²) gates and exact QFT to Θ(n(log n)²) gates. This breakthrough promises significant efficiency gains in quantum computation.