Recent results in the search for new quantum algorithms

A central role in the the theory of quantum algorithms is played by the
Hidden Subgroup Problem where one tries to find the hidden symmetry of a
function that is defined over a group. For different groups this problem
relates to various standard computational problems such as factoring,
counting solutions of finite field equations, lattice problems and graph
isomorphism. In 1994 Peter Shor showed that there exists an efficient
quantum algorithm for the Hidden Subgroup Problem over Abelian groups,
which allowed him to construct his famous algorithm for discrete
logarithms and factoring. Finding similar quantum algorithms for
non-Abelian groups has turned out to be much more difficult.
In this talk I will first give an overview of the Hidden Subgroup
Problem and the quantum algorithm for the Abelian case. After that, I
will describe some of the recent progress on the non-Abelian Hidden
Subgroup Problem, some positive, some negative. Special attention will
be paid to the need to find average case classical algorithms for
problems such as Subset Sum, which are useful as subroutines for quantum
algorithms for Shortest Vector Problems.

Wim van Dam is an assistant professor in computer science and physics at
the University of California, Santa Barbara. His research focuses on the
theory of quantum computation and all things related, with an emphasis
on the development of new quantum algorithms that give an exponential
speed-up when compared with traditional, classical algorithms.

Van Dam received his Ph.D. in Physics from the University of Oxford, UK
in 2000 and in 2002 he received his Ph.D. in Computer Science from the
University of Amsterdam, The Netherlands. Before joining the Computer
Science Department at UCSB in July 2004 and the Physics Department in
July 2005, he was a postdoc at UC Berkeley, HP Labs Palo Alto, The
Mathematical Sciences Research Institute and MIT.