The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups

• URL: http://arxiv.org/abs/2608.05321v1
• Date: Wed, 05 Aug 2026 18:25:25 GMT
• Title: The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups
• Abstract summary: Several early quantum algorithms are instances of the hidden problem (HSP) over finite abelian groups.<n>No-time quantum modularity is known for the HSP over arbitrary non-abelian finite groups.<n>We give a nil-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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=A\rtimes_{\varphi} \mathbb{Z}_{p^k}$, with $A$ finite Abelian, $p$ prime, $k\in \mathbb{N}$ and the action of $\mathbb Z_{p^k}$ is generated by the scalar automorphism $a\mapstoμa$, for some $μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times$, where $\mathrm{Exp}(A)$ is the exponent of $A$. Our algorithm is efficient when $A$ has bounded generator rank and $\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)$. This includes the case $A=\mathbb{Z}_N$ for $N\in\mathbb{N}$ and $k=1$, studied by Bacon, Childs and van Dam (FOCS 2005), and $A=\mathbb{Z}_{q^r}$ with $q$ prime and $r\in \mathbb{N}$ 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 papers

• Extremal Chowla sets and their linear analogues: A human-AI mathematical investigation using Co-Scientist [0.9505505917924889]
  We prove the exact formula $C(L/K)=[L:K]-d_max(L/K)$, where $d_max(L/K)$ is the largest degree over $K$ of a proper intermediate field.<n>For finite fields, we give a direct proof in every degree using a normal-basis construction.
  arXiv  Detail & Related papers  (2026-07-25T01:46:56Z)
• Non-Invertible Symmetries Mixing with Witt Non-Trivial Quantum Cellular Automata [0.0]
  Self-dualities and the stacking of symmetry-protected topological phases are basic operations on quantum many-body systems.<n>We realize this entire structure microscopically as quantum cellular automata acting on a certain local operator algebra.
  arXiv  Detail & Related papers  (2026-07-23T18:00:00Z)
• The structure of gauge invariant Gaussian quantum operations on finite Fermion systems [0.0]
  We study semigroups of quantum operations on $mathscr G_mathcal H_GIG$.<n>Each $etmathscr L$ is one-to-one, and our first main result is a structure theorem for such quantum operations on $mathscr G_mathcal H_GIG$.
  arXiv  Detail & Related papers  (2026-05-01T17:00:29Z)
• Discrete symmetries in classical and quantum oscillators [51.56484100374058]
  We show the eigenfunctions $_n=zn$ of the quantum Hamiltonian in the complex Bargmann-Fock-Segal representation.<n>The superposition $=sum_n c_n_n$ arises only with incomplete knowledge of the initial data for solving the Schrdinger equation.
  arXiv  Detail & Related papers  (2026-01-05T10:04:39Z)
• Probabilistic Bounds on the Number of Elements to Generate Finite Nilpotent Groups and Their Applications [4.250782756734906]
  We prove that $varphi_k(G) ge 1 - $ if $k ge operatornamerank(G) + lceil log(2/) rceil$ (a bound based on the group rank) or if $k ge operatornamelen(G) + lceil log (1/) rceil$ (a bound based on the group chain length)
  arXiv  Detail & Related papers  (2025-11-23T12:30:46Z)
• The hidden subgroup problem for infinite groups [0.0]
  We show that HSP is NP-hard for the additive group of rational numbers, and for normal subgroups of non-abelian free groups.<n>We generalize the ShorKitev algorithm for HSP in $mathbbZk$ with standard query cost.<n>It follows that HSP in any finitely generated, virtually abelian group also has a stretched exponential time algorithm.
  arXiv  Detail & Related papers  (2025-07-24T15:16:20Z)
• Antiparticles in non-relativistic quantum mechanics [55.2480439325792]
  Non-relativistic quantum mechanics was originally formulated to describe particles.<n>We show how the concept of antiparticles can and should be introduced in the non-relativistic case without appealing to quantum field theory.
  arXiv  Detail & Related papers  (2024-04-02T09:16:18Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem [1.189332466445755]
  We present a-time quantum algorithm for the Hidden Subgroup Problem over $mathbbD_2n$. By focusing on structure encoded in the codomain of the problem, we develop an algorithm which uses this structure to direct a "walk" down the subgroup lattice of $mathbbD_2n$ terminating at the hidden subgroup.
  arXiv  Detail & Related papers  (2022-02-19T23:51:15Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.