The dihedral hidden subgroup problem

I’m at the QIP (quantum information processing) 2005 workshop in Boston, which is being hosted by MIT.

I’m not going to be blogging the workshop, but might mention a few tidbits here and there.

In this morning’s session, Andrew Childs gave a talk about the dihedral hidden subgroup problem (DHSP).

This is an important problem: it’s likely to be hard on a classical computer, and it’s widely regarded as a good candidate for efficient solution on a quantum computer. It’s also connected to important problems in computer science, like finding the shortest vector in a lattice, which have cryptographic applications.

It’s a little difficult to give a brief and accessible overview of what the DHSP is about, but I can at least sketch what progress Andrew and his collaborators have made toward a fast quantum algorithm.

In the first part of his talk, Andrew showed that the DHSP can be reduced to performing a measurement to distinguish certain easily-prepared quantum states.

The difficulty of DHSP then lies in (a) figuring out whether there even exists a measurement which is capable of distinguishing those states, (b) if one does exist, figuring out what the best measurement is (or at least a pretty good one), and (c) figuring out whether or not that measurement can be implemented efficiently on a quantum computer.

Andrew answered part (a) and (b), explicitly constructing a measurement (the “pretty good measurement”) which he can prove is the best possible measurement for distinguishing those states.

Andrew has also made some progress on part c, but no efficient implementation yet exists. Nonetheless, solving part (a) and (b) does represent encouraging progress on this important problem.