6
$\begingroup$

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?

$\endgroup$
  • 1
    $\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$ – Sanchayan Dutta Nov 28 '19 at 6:50
  • $\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 '19 at 7:22
  • 1
    $\begingroup$ I understand; I'm not aware of those special cases as such but this and this seem to be some such. $\endgroup$ – Sanchayan Dutta Nov 28 '19 at 7:37

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.