Research:The Hidden Subgroup Problem

What new computational tasks can quantum computers perform more efficiently than their classical bretheren? This question is extremely ambitious and is perhaps one which is too big for anyone to ever fully answer. At the same time there is a great need to find new algorithms where quantum computer outperform classical computers. We are interested in finding these new algorithms.

We have focused our initial investigations into new quantum algorithms in the area of nonabelian hidden subgroup problems. An ongoing project focuses on extracting out the crux of why certain nonabelian hidden subgroup problems are efficiently solvable. Efficient quantum algorithms for these problems are important as they could lead to efficient quantum algorithms for graph isomorphism and certain unique-k-shortest vector in a lattice problems.