Return to Colloquia & Seminar listing
Quantum algorithms for hidden subgroup problemsMathematical 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).