Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

This talk will be about a quantum algorithm for quantum computers. Such an algorithm is interesting when it provides a quantum acceleration, i.e., if it is known or conjectured to be faster than any classical algorithm for the same task. The two most famous quantum algorithms are Grover's algorithm, which can do a brute-force search among N things in time O(sqrt(N)); and Shor's algorithm, which can find the period P of a periodic function on the integers in polynomial time in log(P). (As an application, it can factor numbers in polynomial time.)

I will describe a new algorithm that can determine if two functions on the integers differ by a shift S in time 2^O(sqrt(log(S))). This is an intermediate quantum acceleration, between the quadratic acceleration of Grover's algorithm and the exponential acceleration of Shor's algorithm. Along the way, I will outline what quantum computers are, or would be if they existed, and what kinds of algorithms they can run. This be a one-hour version of what I gave three years ago as a two-part talk. We may conjecture that it will be more polished.