Mathematics Colloquia and Seminars

Given a function $f:G \to S$ on a group which is periodic with respect to a subgroup $H$, the hidden subgroup problem is the computational problem of finding $H$ from values of $f$. It is a challenge problem in quantum computing that generalizes Shor's algorithm. Shor's algorithm is the case $G = \mathbb{Z}$, finding the period of an infinite periodic sequence, and it yields among its many applications a fast quantum algorithm to factor numbers. Much of the progress on the hidden subgroup problem since Shor's stunning paper has been for finite groups. I will outline new results for this problem for infinite groups, including both hardness results and new quantum algorithms.