Quantum Computation and Information Seminar 

14/07/2005, 15:00 — 16:00 — Room P4.35, Mathematics Building
Umesh Vazirani, U California, Berkeley

Quantum algorithms: The non-abelian hidden subgroup problem

The status of the non-abelian hidden subgroup problems is one of the most fundamental open problems in quantum computation today. In particular, the graph automorphism problem may be formulated as hidden subgroup problem over the symmetric group $S_n$, and the shortest lattice vector problem as the hidden subgroup problem over the dihedral group $D_n$. It is natural to try to mimic the success of quantum algorithms for the abelian hidden subgroup problem (which include factoring and discrete log as special cases) for the non-abelian case. This involves Fourier transforms over nonabelian groups which are defined in terms of the irreducible complex representations of the group. In this talk I will describe what we have learnt about such algorithms in the last few years for both the dihedral and symmetric groups.