Seminário de Computação e Informação Quântica 

14/07/2005, 15:00 — 16:00 — Sala P4.35, Pavilhão de Matemática
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.