Fourier Transforms, Quantum Algorithms, and Complexity

Umesh Vazirani

Quantum computation touches upon the foundations of computer science, since quantum computers appear to violate the modern Church-Turing thesis. Quantum computers can perform certain tasks, such as factoring, exponentially faster than classical computers. Over the last couple of years, we have achieved a deeper understanding of quantum algorithms in terms of properties of Fourier transforms over discrete groups. This talk will provide a survey of the field from this viewpoint. The talk is intended for a general audience.

created Thu Mar 2 11:46:54 PST 2000