Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Quantum algorithms for hidden subgroup problems

Mathematical Physics & Probability

Speaker: Greg Kuperberg, UC Davis
Location: 693 Kerr
Start time: Tue, Feb 18 2003, 3:10PM

Among the discoveries that ushered in modern quantum computation, perhaps the most surprising are algorithms that appear to perform certain computations faster than is classically possible. If we accept a "black box" computational model, then the gap between classical and quantum computational complexity theory can actually be proved. For example, Shor's period-finding algorithm takes as input a periodic function f(x) = f(x+p) and finds the period p in polynomial time in log(p), while any classical algorithm requires on the order of sqrt(p) values of f. I will review some of the elements of quantum complexity theory and then describe a new algorithm for the hidden cyclic shift problem f(x) = g(x+p).