Greg Kuperberg

Shor's algorithm, which is a fundamental result in theoretical 
quantum computing, miraculously finds the period of a periodic function 
on the integers, in quantum polynomial time in the number of digits of 
the answer.  The problem that Shor's algorithm solves generalizes to the 
hidden subgroup problem, whereby a function f on a group G is H-periodic 
for some unknown subgroup H, and the problem is to calculate H given 
access to f.  This problem varies tremendously depending on both G and 
H; it is seen as harder when G is highly noncommutative, but easier when 
H is normal.   I will discuss my result that if G is a non-abelian free 
group and H is assumed to be normal, then the hidden subgroup problem is 
NP-hard and a Shor-type algorithm is implausible.  The proof depends on 
the structure theory of small-cancellation groups.  Among other things, 
I will discuss an efficient algorithm to compute a merged form for all 
geodesic words for an arbitrary group element in a small-cancellation group.