{"id":160,"date":"2005-01-14T03:52:54","date_gmt":"2005-01-13T17:52:54","guid":{"rendered":"http:\/\/michaelnielsen.org\/?p=160"},"modified":"2005-01-14T03:52:54","modified_gmt":"2005-01-13T17:52:54","slug":"the-dihedral-hidden-subgroup-problem","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/blog\/the-dihedral-hidden-subgroup-problem\/","title":{"rendered":"The dihedral hidden subgroup problem"},"content":{"rendered":"<p>I\u2019m at the <a title=\"QIP 2005 - the 8th workshop on Quantum Information Processing\" href=\"http:\/\/stuff.mit.edu\/afs\/athena\/org\/q\/qip2005\/\">QIP (quantum information processing) 2005<\/a> workshop in Boston, which is being hosted by MIT.<\/p>\n<p>I\u2019m not going to be blogging the workshop, but might mention a few tidbits here and there.<\/p>\n<p>In this morning\u2019s session, Andrew Childs gave a talk about the dihedral hidden subgroup problem (DHSP).<\/p>\n<p>This is an important problem: it\u2019s likely to be hard on a classical computer, and it\u2019s widely regarded as a good candidate for efficient solution on a quantum computer.  It\u2019s also connected to important problems in computer science, like finding the shortest vector in a lattice, which have cryptographic applications.<\/p>\n<p>It\u2019s 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.<\/p>\n<p>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.<\/p>\n<p>The difficulty of DHSP then lies in (a) figuring out whether there even <em>exists<\/em> 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.<\/p>\n<p>Andrew answered part (a) and (b), explicitly constructing a measurement (the \u201cpretty good measurement\u201d) which he can prove is the best possible measurement for distinguishing those states.<\/p>\n<p>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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I\u2019m at the QIP (quantum information processing) 2005 workshop in Boston, which is being hosted by MIT. I\u2019m not going to be blogging the workshop, but might mention a few tidbits here and there. In this morning\u2019s session, Andrew Childs gave a talk about the dihedral hidden subgroup problem (DHSP). This is an important problem:&hellip; <a class=\"more-link\" href=\"https:\/\/michaelnielsen.org\/blog\/the-dihedral-hidden-subgroup-problem\/\">Continue reading <span class=\"screen-reader-text\">The dihedral hidden subgroup problem<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-160","post","type-post","status-publish","format-standard","hentry","category-3","entry"],"_links":{"self":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/160","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/comments?post=160"}],"version-history":[{"count":0,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/160\/revisions"}],"wp:attachment":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/media?parent=160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/categories?post=160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/tags?post=160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}