Quantum Institute: Visitor Schedule

The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.

December 13, 2007
Thursday, 12:30 PM to 2 PM

Gorjan Alagic,
University of Connecticut

Quantum Algorithms for Product Groups

Abstract

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.