An Introduction to Quantum Computing and the Fourier Transform
Speaker: Lawrence Ip, University of California, Berkeley
When: 2003-12-16 10:00:00
Venue: 78-420
Host: Prof Michael Nielsen
Abstract:The Fourier transform is one of the most widely used algorithms in
practical applications. Some examples include: signal and image
processing, solution of differential equations, routines for
multiplication, and audio and image compression. This ubiquity is
largely due to the availability of a fast implementation (fast
Fourier tranform).
The quantum Fourier transform forms an even more crucial role in the
design of algorithms for quantum computers. In contrast to the
polynomial speedup offered by the classical fast Fourier transform
(O(n^2) -> O(n log n)), the quantum Fourier transform offers an
exponential speedup (O(n^2) -> O(log^2 n)).
I will outline how this exponential speed up is achieved and show
how this forms the basis of Shor's celebrated quantum algorithm for
factoring integers in polynomial time.
Biography:Lawrence Ip obtained his BSc(Hons) in mathematics and BE(Hons) in
electrical engineering from Melbourne University. He is currently a
PhD student in electrical engineering and computer science at the
University of California, Berkeley. His research interests include
quantum computation, and coding and information theory.
Type: ITEE Seminar
Contact:Prof Michael Nielsen, seminar host (nielsen@physics.uq.edu.au)
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)