We know that solving a hidden subgroup problem over a non-commutative group is a long standing problem in quantum computing even for groups like $D_{2n}$ (alternatively can be written as $\mathbb{Z}_n \rtimes \mathbb{Z}_2$) for general $n$. What are some families $n$ for which this can be done?

  • 2
    $\begingroup$ Good question; I was thinking of asking this myself! You might be interested in Greg Kuperberg's 2003 paper which presents a $\mathcal{O}(\exp(\sqrt {C \log N}))$ quantum algorithm for the dihedral subgroup. Note that it is pretty math-heavy and uses representation theory (something that I've been attempting to learn myself). $\endgroup$ Nov 28, 2019 at 6:50
  • 1
    $\begingroup$ I think that is for arbitrary Dihedral group. What I am looking at is some sense, auxiliary problem. This is subexponential algorithm for an arbitrary case. I wanted to know about a special case underlying a polynomial algorithm. $\endgroup$
    – Root
    Nov 28, 2019 at 7:22
  • 3
    $\begingroup$ I understand; I'm not aware of those special cases as such but this and this seem to be some such. $\endgroup$ Nov 28, 2019 at 7:37
  • 1
    $\begingroup$ Greg recently gave a talk, which includes the most recent results in this area youtube.com/watch?v=HdUiO78bVdI $\endgroup$
    – Condo
    Feb 11, 2021 at 18:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.