Quantum Algorithms: Promise, Present and Prospect
Willem Klaas (Wim) van Dam
No enrollment limit, no advance sign up
Participants welcome at individual sessions (series)
Prereq: Linear algebra + basic computer science
See descriptions below for details.
Contact: Timothy F. Havel, NW142218, 2538309, tfhavel@mit.edu
Sponsor: CambridgeMIT Institute
Lecture 1: The Promise
Willem Klaas (Wim) van Dam
I explain what quantum bits and quantum circuits are. Arguments are given why this computational model might be more powerful than classical computing. Some simple toy algorithms are given as well as some general lower bounds.
Wed Jan 21, 1011:00am, NW141112
Lecture 2: The Present
Willem Klaas (Wim) van Dam
An explanation of the quantum Fourier transform is given. Shor's algorithms for the discrete logarithm problem and factoring are described. The extension to the (Abelian) hidden subgroup is mentioned. Other quantum algorithms for Pell's equation, hidden shift problems and Gauss sum estimation are discussed as well.
Thu Jan 22, 1011:00am, NW141112
Lecture 3: The Prospects
Willem Klaas (Wim) van Dam
I will give my point of view of where and how we could find new quantum algorithms. I will describe my work on the relation between quantum computing, the zeros of zeta functions, and approximate point counting of equations over finite fields. Likely other topics are: what about algorithms for problems that have to do with number theory, lattices and combinatorial optimization?
Fri Jan 23, 1011:00am, NW141112
Latest update: 07Jan2004

