The hidden subgroup problem for infinite groups

2025/07/24 by Greg Kuperberg, Kuperberg, Greg · 1 voice · 4 citations
Computer Science · Mathematics · #Abelian group #Discrete logarithm #Exponential function #Finite Group Theory Research #Geometric and Algebraic Topology #Group (periodic table) #Polynomial #Rank (graph theory) #Rank of an abelian group #Time complexity #Torsion subgroup #cs.CC #math.GR #quant-ph

paper · pdf · doi:10.48550/arxiv.2507.18499

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/07/24 · openalex created_date 2025/10/16 · openalex updated_date 2026/08/05

Abstract

Following the example of Shor's algorithm for period-finding in the integers, we explore the hidden subgroup problem (HSP) for discrete infinite groups. On the hardness side, we show that HSP is NP-hard for the additive group of rational numbers, and for normal subgroups of non-abelian free groups. We also indirectly reduce a version of the short vector problem to HSP in ℤ^k with pseudo-polynomial query cost. On the algorithm side, we generalize the Shor-Kitaev algorithm for HSP in ℤ^k (with standard polynomial query cost) to the case where the hidden subgroup has deficient rank or equivalently infinite index. Finally, we outline a stretched exponential time algorithm for the abelian hidden shift problem (AHShP), extending prior work of the author as well as Regev and Peikert. It follows that HSP in any finitely generated, virtually abelian group also has a stretched exponential time algorithm.

Citations

• Strengths and Weaknesses of Quantum Computing
• The Difference Between Consecutive Primes
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Factoring polynomials with rational coefficients

Cited by

• A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective
• One-Query Quantum Algorithms for the Index-q Hidden Subgroup Problem
• Hard Instances of Discrete Logarithm Problem and Cryptographic Applications
• Hybrid oscillator-qudit quantum processors: stabilizer states and symplectic operations

Discussions

• From "The hidden subgroup problem for infinite groups" by Greg Kuperberg. arxiv.org/abs/2507.18499 [bsky, 21 points, 2 comments]

Related

• The Hidden Subgroup Problem
• An Improved Query for the Hidden Subgroup Problem
• A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of\n non-abelian Groups
• Zero sum subsequences and hidden subgroups