The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups
Abstract
Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form G=Artimesφ ℤpk, with A finite Abelian, p prime, k∈ ℕ and the action of ℤpk is generated by the scalar automorphism a↦μa, for some μ∈ℤExp(A)×, where Exp(A) is the exponent of A. Our algorithm is efficient when A has bounded generator rank and Exp(A)/p=polylog(|G|). This includes the case A=ℤN for N∈ℕ and k=1, studied by Bacon, Childs and van Dam (FOCS 2005), and A=ℤqr with q prime and r∈ ℕ studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).
Related
- The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
- Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
- Generating random unitaries by products of conjugated Hamiltonian evolutions
- A simple solution to the monopole problem: SU(5) GUT with symmetry breaking into special subgroup
- On the sample complexity of the generalized hidden shift problem over arbitrary finite groups
BibTeX
@misc{morales2026hidden,
title = {{The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups}},
author = {Mauro E. S. Morales},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.05321},
eprint = {2608.05321},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.05321},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups
AU - Mauro E. S. Morales
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2608.05321
UR - https://arxiv.org/abs/2608.05321
AB - Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form G=Artimes_φ ℤ_p^k, with A finite Abelian, p prime, k∈ ℕ and the action of ℤ_p^k is generated by the scalar automorphism a↦μa, for some μ∈ℤ_Exp(A)^×, where Exp(A) is the exponent of A. Our algorithm is efficient when A has bounded generator rank and Exp(A)/p=polylog(|G|). This includes the case A=ℤ_N for N∈ℕ and k=1, studied by Bacon, Childs and van Dam (FOCS 2005), and A=ℤ_q^r with q prime and r∈ ℕ studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).
ER -