# Status of hidden shift and hidden subgroup problems

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?

• 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). Nov 28 '19 at 6:50
• 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.
– Root
Nov 28 '19 at 7:22
• I understand; I'm not aware of those special cases as such but this and this seem to be some such. Nov 28 '19 at 7:37
• Greg recently gave a talk, which includes the most recent results in this area youtube.com/watch?v=HdUiO78bVdI Feb 11 at 18:57