Skip to content

The dihedral hidden subgroup problem

by Michael Nielsen on January 14, 2005

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.

From → General

  1. I mentioned the QIP 2005 (and your blog post) in QubitNews. There has been a provocative comment, apparently disappointed with the lack of experimental advances or new appealing ideas. ( see comment here: ). If you like to comment on the most interesting or appealing results you find in the workshop (here in your blog), I will be happy to link your comments in QubitNews 🙂

    Furthermore, if anybody attending the workshop wants to comment something about the conferences and/or join the discussion, (s)he will be welcomed!

  2. Hey, it’d be nice if you could put up the slides of the talk you gave at the recent QIP. Even nicer if you had an audio or video recording to share 🙂

  3. Thanks, Michael. It should also be pointed out that this work is joint with Dave Bacon and Wim van Dam. The slides are available at

Comments are closed.