Quantum Fourier transforms for extracting hidden linear structures in finite fields
Niel de Beaudrap, Richard Cleve, John Watrous · arXiv (Cornell University) · 2000
We propose a definition for quantum Fourier transforms in settings where the algebraic structure is that of a finite field, and show that they can be performed efficiently by a quantum computer. Using these finite field quantum Fourier transforms, we obtain the strongest separation between quantum and classical query complexity known to date---specifically, we define a problem that requires\\Omega\\Gammaq n=2) queries in the classical (bounded error) case, but can be solved exactly with a single query in the quantum case using a polynomial number (in n) of auxiliary operations. Finally, we consider quantum Fourier transforms over arbitrary finite rings, and give efficient quantum circuits for implementing quantum Fourier transforms for the particular case of rings of matrices over finite fields.