Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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).