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