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$ Commented 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
    Commented 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$ Commented 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
    Commented Feb 11, 2021 at 18:57

1 Answer 1


Here are some cases where there are polynomial time quantum algorithms for the hidden subgroup problems over non-ableian groups.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.