Status of hidden shift and hidden subgroup problems

Question

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?

Answer 1

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

• When the subgroups that are hidden are all normal. This is due to Hallgren, Russell, and Ta-Shma (2000). In particular this covers Dedekind groups, of which the only non-Ablian ones are a direct product of quaternions, abelian 2-groups and torsion ablian groups with all elements of odd order.
• Metacyclic groups, $Z_N \rtimes Z_p$ and groups of the form $(Z_p)^r \rtimes Z_p$, including the finite Heisenberg group. This is due to Bacon, Childs, and van Dam (2005) (though most the later two authors). The metacyclic group case is a generalization of q-hedral groups which have a polynomial time algorithm due to Moore, Rockmore, Russell, and Schulman (2002).
• Certain "poly-near-hamiltonian" groups. These are groups for which the intersection of the normalizers of the groups are sufficiently large. This was first shown by Grigni, Sehulman. Vazirani and Vazirani (2001) and improved upon by Gavinsky (2004)
• The groups $Z_{p^r} \rtimes Z_q$, where $p$ is an odd prime. This is due to Inui and Le Gall (2004)
• Extraspecial groups due to Ivanyos, Sanselme, Santha (2007). This was extended to nil-2 group by Ivanyos, Sanselme, Santha (2008)
• Borel subgroups of the general linear group when the base field is not much smaller than the degree of the linear group. This is due to Ivanyos (2001)