Quantum Computation and Information Seminar 

02/07/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Cristopher Moore, University of New Mexico

A challenge for quantum computing: the non-Abelian hidden subgroup problem

In 1994, Peter Shor showed that quantum computers can factor integers in polynomial time. The security of RSA public-key encryption relies on the fact that (we believe) classical computers are unable to do this. While the emerging consensus is that quantum computers cannot solve $NP$-complete problems in polynomial time, it seems plausible that they can solve a number of other problems which appear to be outside $P$. One such problem is Graph Isomorphism; namely, telling whether two large graphs are simply permutations of each other. Shor's factoring algorithm relies on the fact that we can relate factoring to finding periodicities in a particular series of integers, which is equivalent to finding a "hidden subgroup" of the cyclic group. If we could do the same thing for the symmetric group $S_n$, i.e. the group of permutations of $n$ things, then we could solve Graph Isomorphism on a quantum computer. However, finding hidden subgroups in non-Abelian groups such as $S_n$ seems to be much harder than doing so in Abelian groups. I will describe recent joint work with Alex Russell, Dan Rockmore and Leonard Schulman on the non-Abelian hidden subgroup problem (HSP). Our work relies on the representation theory of finite groups, which is a generalization of Fourier analysis to the non-Abelian case. I will show that by measuring the high-dimensional representations of a group in a well-chosen basis, we can solve the HSP for a family of non-Abelian groups. However, we still seem very far from solving Graph Isomorphism, and I will comment on the long road ahead.