Computing the symmetries of a function on an abstract group is a
classically difficult problem with a plethora of important applications
such as factoring, discrete logarithm, and graph isomorphism. Quantum
computers have an edge in this area due to their ability to perform the
quantum Fourier transform efficiently. Indeed, the Fourier transform is
precisely the unitary operator that exposes these symmetries by
decomposing the space of functions according to the left (or right)
action
of the group. This procedure is thus the essential ingredient of many
quantum algorithms that outperform their classical counterparts. This is
the case in Shor's algorithms for factoring and discrete logarithm, as
well as Simon's algorithm for computing hidden subgroups in (Z_2)^n -
where the relevant subgroup is hidden in the symmetries of an oracle
function. In this talk, we will discuss the properties of the Fourier
transform on nonabelian groups, and its use in computing subgroups
hidden
in this manner. We will concentrate on recent work (joint with Cris
Moore
and Alex Russell) on the nonabelian generalization of Simon's problem,
i.e., reconstructing subgroups of n-fold products of a fixed nonabelian
group.