Citation: Bacon, Dave, Andrew M. Childs, and Wim van Dam. "From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups." 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). IEEE, 2005.
Web: https://arxiv.org/abs/quant-ph/0504083
Tags: Computer-scientific, Quantum-advantage
This paper is a good starting point for the whole little literature about the hidden subgroup problem over non-abelian groups.
Greg Kuperberg has a subexponential (but superpolynomial) algorithm for the dihedral hidden subgroup problem:
> Kuperberg, Greg. "A subexponential-time quantum algorithm for the dihedral hidden subgroup problem." SIAM Journal on Computing 35.1 (2005): 170-188.
> Regev, Oded. "A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space." arXiv preprint quant-ph/0406151 (2004).
> Kuperberg, Greg. "Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem." arXiv preprint arXiv:1112.3333 (2011).
An early attempt at this dihedral problem came in a paper of Ettinger-Hoyer, where they showed that there is an algorithm which uses a polynomial number of oracle calls but an exponential amount of runtime:
> Ettinger, Mark, and Peter Høyer. "On quantum algorithms for noncommutative hidden subgroups." Annual Symposium
This paper gives a somewhat generael framework for determining if it is possible to solve the hidden subgroup problem on a given group. They give applications to several families. I am curious about the fact that they are able to solve the hidden subgroup problem over non-abelian groups. This is counter to my intuition from topological quantum computing, where the sharp divide seems to be between nilpontent and non-nilpotent groups. There's a lot of explanations of this. Maybe there's good quantum computing algorithms for metaabelian groups? Maybe this paper is "creating" in a way I haven't been able to grok? Maybe the correspondence between levels of abelianness and quantum complexity isn't as universal as I thought?