#### Theory Seminar

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