12

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?

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

0 Answers0