The hidden subgroup problem for infinite groups

• URL: http://arxiv.org/abs/2507.18499v1
• Date: Thu, 24 Jul 2025 15:16:20 GMT
• Title: The hidden subgroup problem for infinite groups
• Authors: Greg Kuperberg,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\mathbb{Z}^k$ with pseudo-polynomial query cost. On the algorithm side, we generalize the Shor-Kitaev algorithm for HSP in $\mathbb{Z}^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.

Related papers

• An Initialization-free Quantum Algorithm for General Abelian Hidden Subgroup Problem [0.0]
  Our algorithm can adopt an arbitrary unknown mixed state as the auxiliary register.<n>Our algorithm also restores the state of the auxiliary register to its original form after completing the computations.
  arXiv  Detail & Related papers  (2025-07-24T04:50:28Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace.<n>We introduce the generative leap exponent $kstar$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting.
  arXiv  Detail & Related papers  (2025-06-05T18:34:56Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Zero sum subsequences and hidden subgroups [2.5204420653245245]
  We solve the hidden subgroup problem in nilpotent groups by transforming a subgroup to its images in the quotient groups by the members of a central series. Knowing this image allows one to descend to a proper subgroup unless the hidden subgroup is the full group. We present a new deterministic time algorithm for the latter problem in the case of the size of the field is constant.
  arXiv  Detail & Related papers  (2023-04-17T15:40:30Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• 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)
• Polynomial-time quantum algorithm for solving the hidden subgroup problem [0.0]
  The hidden subgroup problem(HSP) is one of the most important problems in quantum computation. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum algorithm.
  arXiv  Detail & Related papers  (2022-04-07T08:50:50Z)
• 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)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals. For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
  arXiv  Detail & Related papers  (2020-06-22T17:53:54Z)
• The Hidden Subgroup Problem for Universal Algebras [0.7832189413179361]
  The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete discrete problem, graph isomorphism, and the shortest vector problem.
  arXiv  Detail & Related papers  (2020-01-30T13:09:35Z)

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.