Fact-checked by Grok 2 weeks ago

Hidden subgroup problem

The hidden subgroup problem (HSP) is a central challenge in quantum computing, defined as follows: given a finite group G, a set S, and access to a function f: G \to S that is constant on the left cosets of some unknown subgroup H \leq G and distinct on different cosets, the task is to identify H (or a generating set for it).^[1] This problem provides a unifying framework for many quantum algorithms that achieve exponential speedups over classical counterparts.^[1] The HSP gained prominence through its connections to landmark quantum algorithms. For instance, Simon's algorithm solves a specific instance of the HSP over the abelian group \mathbb{Z}_2^n, where the hidden subgroup is of order 2, enabling the efficient identification of a hidden string s that underlies a function with period s.^[2] Similarly, Shor's algorithm for integer factorization and the discrete logarithm problem reduces to solving the HSP over abelian groups like \mathbb{Z}_N or products of cyclic groups, using period-finding to reveal the order of the hidden subgroup.^[1] These reductions highlight the HSP's role in breaking certain classical cryptographic schemes, such as RSA, by leveraging quantum parallelism.^[1] The standard approach to solving the HSP involves quantum Fourier sampling, which works efficiently for abelian groups. In this method, a quantum computer prepares a uniform superposition over group elements, applies the function f via an oracle to create coset states, measures to collapse to a random coset, and then applies the quantum Fourier transform over G to extract information about the orthogonal complement of H.^[2] Repeating this process O(\log |G|) times yields enough samples to reconstruct H with high probability, requiring only polynomial resources in \log |G|.^[1] This technique, formalized in works like the EHK algorithm, succeeds for all abelian groups and has been implemented for problems like period finding in O(\log N) steps for G = \mathbb{Z}_N.^[2] For non-abelian groups, however, the HSP remains largely unsolved, posing significant open challenges. Instances over the dihedral group D_N relate to lattice problems like the shortest vector problem, with subexponential algorithms (e.g., Kuperberg's method running in $2^{O(\sqrt{\log N})}) but no polynomial-time solutions.^[1] The symmetric group S_n version connects to graph isomorphism, requiring \Omega(n \log n) entangled measurements in the worst case.^[1] Progress on these cases could impact fields beyond computing, including chemistry (via molecular simulation) and cryptography (e.g., breaking code-based schemes).^[1] Overall, the HSP exemplifies the power and limitations of quantum algorithms, driving ongoing research into group-theoretic quantum speedups.^[2]

Definition

Formal Statement

The hidden subgroup problem (HSP) is a fundamental computational problem in group theory and quantum information science. Given a finite group G, there exists an unknown subgroup H \leq G. A function f: G \to S is provided, where S is a finite set, such that f is constant on each left coset of H and takes distinct values on distinct left cosets of H.^[3] Mathematically, this means that for all g, g' \in G,

f(g) = f(g') \iff g^{-1} g' \in H.

The objective is to identify a generating set for the subgroup H.^[3] Access to the function f is provided in a black-box model via an oracle, which allows evaluation of f at specified group elements. The computational complexity of solving the HSP is typically measured by the number of oracle queries required, along with the time needed to perform group operations and process the results.^[4]

Variations and Assumptions

The hidden subgroup problem (HSP) is typically formulated under the assumption that the group G is finite and its order |G| is known, with access to a function f: G \to S provided via a black-box oracle, where S is a finite set, and f is promised to be constant on the left cosets of some nontrivial subgroup H \leq G and takes distinct values on distinct cosets (i.e., f is injective on G/H).^[5] This setup ensures that the problem is well-posed as a promise problem, where the input satisfies the condition that such an H exists, and the goal is to identify generators for H.^[2] A key variation arises in the structure of the group G: when G is abelian, every subgroup H is normal, simplifying the coset structure since left and right cosets coincide, and G/H forms a group under the induced operation.^[6] In contrast, for non-abelian G, H need not be normal, leading to distinctions between left and right cosets; many formulations of the non-abelian HSP therefore restrict to normal subgroups or focus on identifying the normal core of H (the largest normal subgroup contained in H) or on preparing uniform superpositions over cosets to extract representation-theoretic information.^[6] Other variations relax the exactness of the promise or the oracle model. In the approximate HSP, the function f is only nearly constant on cosets (e.g., within \epsilon variation) rather than exactly constant, which arises naturally in settings with noise or in extensions to infinite groups where exact periodicity is approximated.^[7] The problem can also be posed as a search version (output generators of H) or decision version (verify if a given subgroup hides), and oracles may return classical values (limiting to sequential queries) or quantum superpositions (enabling parallel evaluation via unitaries like U_f |g\rangle |0\rangle = |g\rangle |f(g)\rangle).^[8] In the black-box setting, the classical query complexity of the HSP is \Omega(\sqrt{|G|}), as established by lower bounds analogous to those for Simon's problem over \mathbb{Z}_2^n.^[9] Quantum algorithms achieve polylogarithmic query complexity, specifically O(\log^4 |G|), for identifying H with high probability in any finite group G, though the overall time complexity remains exponential due to group-theoretic computations.^[8]

Background and Motivation

Group Theory Essentials

A group G is a nonempty set equipped with a binary operation \cdot: G \times G \to G that satisfies closure, associativity, the existence of an identity element e \in G such that g \cdot e = e \cdot g = g for all g \in G, and the existence of inverses, so that for each g \in G there is g^{-1} \in G with g \cdot g^{-1} = g^{-1} \cdot g = e.^[10] Groups often arise in algebraic structures, such as symmetries of geometric objects or integers under addition. A subgroup H of a group G is a nonempty subset H \subseteq G that is itself a group under the restricted operation from G, containing the identity e and closed under the operation and inverses.^[10] Proper subgroups exclude the trivial cases \{e\} and G itself in some contexts.^[11] Cosets provide a way to partition the group relative to a subgroup. For a subgroup H \leq G, the left coset of H generated by g \in G is gH = \{ gh \mid h \in H \}, and the right coset is Hg = \{ hg \mid h \in H \}. These cosets form a partition of G, meaning every element of G belongs to exactly one left (or right) coset of H.^[12] The set of all left cosets is denoted G/H, though this notation is also used for the quotient group when defined. If H is a normal subgroup of G (meaning gHg^{-1} = H for all g \in G, or equivalently left and right cosets coincide), then G/H forms a group under the operation (g_1 H)(g_2 H) = (g_1 g_2) H, called the quotient group.^[13] The coset decomposition of G by right cosets of H is given by

G = \bigcup_{g \in G/H} Hg,

where the union is disjoint.^[14] An abelian group is a group G where the operation is commutative, so gh = hg for all g, h \in G.^[12] Examples include the cyclic group \mathbb{Z}_n of integers modulo n under addition, which has order n and is generated by 1, and the elementary abelian group (\mathbb{Z}_p)^n, the vector space of dimension n over the finite field \mathbb{F}_p (with p prime), where every non-identity element has order p.^[15]^[16] Group representations generalize homomorphisms to matrix groups, providing a way to study groups via linear algebra. A representation of a finite group G is a homomorphism \rho: G \to \mathrm{GL}(V) for some finite-dimensional vector space V over \mathbb{C}; it is irreducible if V has no proper nontrivial invariant subspace under \rho(g) for all g \in G.^[17] For non-abelian groups, irreducible representations can have dimension greater than 1, capturing the group's non-commutativity.^[18] In contrast, for abelian groups, all irreducible representations are 1-dimensional, corresponding to characters \chi: G \to \mathbb{C}^\times, which are group homomorphisms to the multiplicative group of nonzero complex numbers; the character theory of abelian groups uses these to decompose representations and analyze the group structure.^[19] For a finite abelian group G, the dual group \hat{G} consists of all characters of G, forming a group under pointwise multiplication that is isomorphic to G itself via Pontryagin duality.^[20] In Fourier analysis on finite abelian groups, this duality identifies the quotient G/H (for H \leq G) with the dual of the annihilator subgroup H^\perp = \{\chi \in \hat{G} \mid \chi(h) = 1 \ \forall h \in H\} in \hat{G}, enabling transforms over cosets.^[20]

Role in Quantum Computing

The hidden subgroup problem emerged in the 1990s as a generalizing framework for quantum algorithms addressing tasks like period-finding and parity checks, building on early quantum query models. It was implicitly utilized in Peter Shor's 1994 development of algorithms for integer factoring and discrete logarithms, where subgroup identification underpins the core periodicity detection step. The problem was formally articulated in Ethan Bernstein and Umesh Vazirani's 1997 analysis of quantum complexity, establishing it as a benchmark for quantum advantage.^[21] In quantum computing, the hidden subgroup problem provides a unifying structure for numerous algorithms that achieve superpolynomial speedups, with problems such as integer factoring and the discrete logarithm reducible to specific abelian instances of the HSP. This reduction highlights how diverse cryptographic and computational challenges share a common group-theoretic foundation, enabling quantum methods to exploit symmetries for efficient resolution.^[22] Classically, the HSP resists efficient solution due to its resemblance to unstructured search, typically demanding an exponential number of queries proportional to the group order to identify the hidden subgroup. Quantum approaches, however, resolve abelian cases in polynomial time through constructive interference in superposition states, yielding exponential accelerations relative to classical exhaustive enumeration.^[23] At its core, the HSP formalizes symmetry-finding in finite groups, a capability that quantum computation uniquely amplifies by revealing latent structures that classical algorithms overlook, thus powering breakthroughs in areas from number theory to optimization.^[23]

Algorithms for Abelian Groups

Quantum Fourier Transform

The quantum Fourier transform (QFT) is a unitary linear transformation that plays a central role in solving the hidden subgroup problem for finite abelian groups, serving as the quantum analog of the classical discrete Fourier transform. For a finite abelian group G, the QFT acts on the computational basis states |g\rangle (where g \in G) by mapping them to states in the dual basis |\chi\rangle (where \chi \in \hat{G}, the dual group consisting of all irreducible characters of G). Specifically, it transforms |g\rangle to \frac{1}{\sqrt{|G|}} \sum_{\chi \in \hat{G}} \chi(g) |\chi\rangle, where characters \chi: G \to \mathbb{C}^\times are group homomorphisms satisfying \chi(gh) = \chi(g)\chi(h) for all g, h \in G, and the normalization ensures unitarity.^[24] This definition leverages the fact that the characters form an orthonormal basis for the group algebra \mathbb{C}[G], with inner product \langle \chi, \psi \rangle = \frac{1}{|G|} \sum_{g \in G} \overline{\chi(g)} \psi(g) = \delta_{\chi, \psi}.^[25] In the special case of cyclic groups G = \mathbb{Z}_n, the QFT reduces to a Hadamard-like transform familiar from Shor's algorithm. Here, the characters are given by \chi_j(k) = \omega^{jk} for j, k = 0, \dots, n-1 and \omega = e^{2\pi i / n}, a primitive nth root of unity. The transformation matrix has entries F_{jk} = \frac{1}{\sqrt{n}} \omega^{jk}, so |j\rangle \mapsto \frac{1}{\sqrt{n}} \sum_{k=0}^{n-1} \omega^{jk} |k\rangle. This form was introduced in the context of quantum factoring and remains the standard implementation for cyclic structures. A key property of the QFT over abelian groups is that it diagonalizes the convolution operation in the group algebra: if f * h(g) = \sum_{x \in G} f(x) h(x^{-1}g), then the Fourier transform satisfies \widehat{f * h}(\chi) = \hat{f}(\chi) \hat{h}(\chi) for all \chi \in \hat{G}. This diagonalization facilitates efficient computation of periodic functions and is essential for extracting hidden periodicities. Additionally, the QFT enables quantum phase estimation by approximating the eigenvalues of unitary operators through Fourier sampling, allowing the recovery of phase information with high precision in superposition states.^[24] The full QFT operator can be expressed as

F_G = \frac{1}{\sqrt{|G|}} \sum_{g \in G} \sum_{\chi \in \hat{G}} \chi(g) |\chi\rangle \langle g|,

which is unitary since \hat{G} \cong G as groups.^[25] Implementing the QFT on a quantum computer requires a circuit that encodes the group elements efficiently, typically using \log_2 |G| qubits. For general finite abelian groups (decomposable as direct products of cyclic groups via the fundamental theorem), the QFT can be constructed recursively by applying component-wise QFTs and controlled phase gates. The circuit uses phase gates R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^k} \end{pmatrix} and controlled operations, achieving a gate complexity of O((\log |G|)^2) for exact computation over groups like \mathbb{Z}_{2^m}. This quadratic scaling in the number of qubits makes it feasible for practical quantum algorithms despite the exponential state space.^[24]

Standard Solving Procedure

The standard solving procedure for the hidden subgroup problem (HSP) over finite abelian groups relies on the quantum Fourier transform (QFT) to efficiently identify the hidden subgroup H \leq G using a black-box oracle for the function f: G \to S that is constant on cosets of H and distinct on different cosets. This algorithm, which generalizes techniques from Shor's factoring algorithm, achieves polynomial-time performance in \log |G| for groups where the QFT and group operations are efficient.^[26] The procedure begins by preparing a uniform superposition over the group elements in the first register, initialized with the second register in |0\rangle:

\frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle |0\rangle.

Next, the oracle U_f is applied to compute f(g) in the second register:

\frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle |0\rangle \xrightarrow{U_f} \frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle |f(g)\rangle.

Measuring the second register yields a value c = f(g_0) for some g_0 \in G, collapsing the first register to a uniform superposition over the coset g_0 H:

\frac{1}{\sqrt{|H|}} \sum_{h \in H} |g_0 h\rangle |c\rangle.

The QFT is then applied to the first register, transforming the coset state into a superposition peaked over characters \chi \in \hat{G} (the dual group) that annihilate H, i.e., \chi(h) = 1 for all h \in H. Measuring the first register obtains such a character \chi with high probability.^[26] To recover H, the algorithm is repeated O(\log |G|) times independently, yielding a set of characters whose common kernel is the annihilator H^\perp = \{\chi \in \hat{G} \mid \chi(h) = 1 \ \forall h \in H\}. Since G is abelian and finite, H can then be computed as the annihilator of H^\perp, or equivalently via solving a system of linear equations over the characters to find generators of H. Each run succeeds in reducing the uncertainty about H by a constant factor with constant probability, ensuring high overall success probability after O(\log |G|) iterations. The query complexity is O(\log |G|), as each iteration requires one oracle call, and the total time complexity is polylogarithmic in |G|, assuming efficient implementations of the QFT (which takes O((\log |G|)^2) gates) and classical post-processing for kernel intersection (polynomial in \log |G|).^[26] This efficiency holds for abelian groups like \mathbb{Z}_N or products thereof, where the dual group structure allows straightforward computation.

Specific Instances

Simon's Problem

Simon's problem is a foundational instance of the abelian hidden subgroup problem, defined over the finite abelian group G = (\mathbb{Z}_2)^n. Here, a secret element s \in G (with s \neq 0) defines the hidden subgroup H = \{0, s\}, and an oracle provides access to a function f: G \to \{0,1\}^m (where m \geq n) that is periodic with period s, meaning f(x) = f(y) if and only if x \oplus y \in H. The function is promised to be either one-to-one (corresponding to s = 0) or to have exactly this nontrivial period s, and the goal is to determine s.^[26]^[27] The quantum algorithm solves this HSP instance by applying the standard procedure for abelian groups, employing the quantum Fourier transform over (\mathbb{Z}_2)^n, known as the Walsh-Hadamard transform. It begins by creating a uniform superposition over the group elements, queries the oracle to attach f(x), and then applies the transform to the input register. Measuring the result yields a character y \in G satisfying y \cdot s = 0 over \mathbb{Z}_2, providing a linear equation orthogonal to s. Repeating this O(n) times generates a system of independent equations, which can be solved classically in O(n^3) time to recover s. Overall, the algorithm requires O(n) oracle queries and runs in polynomial time.^[27] In stark contrast, classical algorithms—whether deterministic or randomized—require \Omega(2^{n/2}) queries to solve Simon's problem with constant success probability, establishing an exponential quantum speedup. This query separation arises because finding colliding inputs under f classically demands roughly the square root of the domain size to guarantee a collision via the birthday paradox, after which multiple collisions are needed to resolve s.^[28] Introduced by Daniel Simon in 1994, this algorithm provided the first oracle relative separation between quantum and classical complexity classes, proving that \mathrm{[BQP](/page/BQP)} \not\subseteq \mathrm{BPP}.^[27]

Shor's Factoring Algorithm

Shor's algorithm for integer factorization leverages the hidden subgroup problem (HSP) over abelian groups to achieve a quantum speedup. To factor a composite integer N, the algorithm first selects a random integer a coprime to N. It then solves for the order r of a modulo N, defined as the smallest positive integer such that a^r \equiv 1 \pmod{N}. This order-finding subroutine is formulated as an HSP instance on the additive group G = \mathbb{Z}_N, where the function is f(x) = a^x \mod N and the hidden subgroup is H = \{ kr \mid k = 0, \dots, r-1 \} = r \mathbb{Z}_N.^[29] The function f(x) is constant on the cosets of H, meaning f(x) = f(y) whenever x - y \in H. Solving this HSP involves applying the quantum Fourier transform (QFT) over \mathbb{Z}_N to a superposition of function evaluations, which reveals the hidden subgroup through phase estimation. The QFT output exhibits peaks at frequencies that are integer multiples of N/r, allowing efficient recovery of r with high probability using phase estimation techniques. Once r is obtained, if r is even and a^{r/2} \not\equiv -1 \pmod{N}, the greatest common divisors \gcd(a^{r/2} - 1, N) and \gcd(a^{r/2} + 1, N) yield non-trivial factors of N. This probabilistic procedure succeeds with probability at least 1/2, and repetition ensures reliability.^[29] The algorithm runs in polynomial time, specifically O((\log N)^3) quantum gates, providing an exponential speedup over the best known classical algorithms, which require subexponential time such as O(\exp((\log N)^{1/3} (\log \log N)^{2/3})) via the general number field sieve. In his seminal 1994 work, Peter Shor demonstrated that integer factorization belongs to the complexity class BQP using this HSP-based approach, establishing a foundational result in quantum computing.^[29]

Non-Abelian Extensions

General Challenges

Unlike the abelian case, where the hidden subgroup problem (HSP) can be solved efficiently using the quantum Fourier transform (QFT) over a single canonical basis, no general efficient quantum algorithm exists for non-abelian groups.^[30] In non-abelian settings, the group Fourier transform operates over irreducible representations (irreps) of varying dimensions greater than one, lacking a unique orthonormal basis analogous to the abelian character table.^[30] A core difficulty arises in identifying the hidden subgroup H from superpositions of coset states: the quantum algorithm produces states in the Fourier domain concentrated on irreps trivial on H, but measuring these yields a random basis vector within the irrep subspace, causing an irreversible collapse that obscures the necessary decomposition into irreps supported only on cosets of H.^[30] Random basis choices in these measurements provide only exponentially small information about H, requiring an impractically large number of samples—on the order of \left( \sqrt{|G|/|H|} / \sqrt{\chi(G)} \right)^{1/3}, where \chi(G) is the number of conjugacy classes—to distinguish the hidden subgroup with high probability.^[30] The non-abelian HSP is widely believed to be computationally hard, with strong connections to problems such as graph isomorphism and learning permutations, both of which lack efficient classical or quantum solutions in general.^[30] For the symmetric group S_n, the classical HSP is intractable, requiring exponential time due to the group's size n!, and its decision version remains open but is suspected to be at least as hard as NP-intermediate problems like graph isomorphism, with no known polynomial-time quantum algorithm.^[30]^[1] Significant no-go results demonstrate that the standard Fourier sampling approach fails for most non-abelian groups: even with optimal measurements, the method cannot efficiently extract the subgroup structure when irreps have high multiplicity or dimension, as shown in analyses from the early 2000s.^[30]

Algorithms for Special Cases

For the dihedral group D_n, which represents the symmetries of a regular n-gon consisting of rotations and reflections, no polynomial-time quantum algorithm is known for the HSP. However, Greg Kuperberg developed a subexponential-time quantum algorithm in 2005 that solves it with time and query complexity $2^{O(\sqrt{\log n})}.^[31] This approach involves repeated pairing of qubits to improve the representation and ultimately identify the hidden subgroup generated by a reflection. Wreath products of groups, such as the iterated wreath product \mathbb{Z}_2 \wr \mathbb{Z}_2 \wr \cdots \wr \mathbb{Z}_2, admit efficient quantum algorithms for solving the hidden subgroup problem, particularly in the context of iterated HSP instances that arise in learning hidden permutations or symmetric functions. These algorithms achieve polynomial-time solutions by recursively decomposing the problem using the group's structure, with query complexity scaling as O(\log^k n) for k-fold iterations, making them applicable to cryptographic and learning-theoretic settings.^[32] The Heisenberg group over finite fields, a nilpotent non-abelian group exemplified by the group of upper-triangular 3x3 matrices with ones on the diagonal modulo a prime, can be solved via quantum algorithms that exploit abelianization or irreducible representation theory. By mapping to the abelian quotient or using Fourier analysis over representations, the hidden subgroup is identifiable in polynomial time, with the algorithm's efficiency tied to the group's low-dimensional representations.^[33] In 2004, Mark Ettinger, Peter Høyer, and Emanuel Knill showed that the quantum query complexity of the HSP is polynomial in \log |G| for any finite group G, meaning a polynomial number of oracle queries suffices to identify H with certainty. However, the computational overhead for non-abelian groups remains a challenge, though this result enables efficient solutions for subclasses where representation theory allows fast processing, such as certain extraspecial groups.^[34]

Recent Developments

Experimental Demonstrations

Experimental demonstrations of abelian hidden subgroup problem (HSP) algorithms have advanced significantly on noisy intermediate-scale quantum (NISQ) hardware, focusing on instances like Simon's problem and Shor's factoring algorithm. These implementations highlight the potential for quantum speedup while grappling with noise and limited qubit counts. Early efforts targeted small-scale systems to validate the standard solving procedure, which involves coset state preparation, quantum Fourier transform application, and measurement. Simon's problem, a canonical abelian HSP, has been experimentally realized on NISQ devices. In 2021, researchers implemented Simon's algorithm on IBM quantum processors using 4-qubit circuits, demonstrating noise compensation techniques that improved success probabilities for identifying the hidden string, despite decoherence effects. Subsequent benchmarks in 2024 extended this to IonQ trapped-ion systems, benchmarking up to 17 qubits and observing error rates that scale linearly with problem size, confirming challenges in maintaining accuracy for larger instances. These experiments used up to 127 qubits on IBM hardware for larger variants, underscoring progress in error mitigation for HSP oracles. Shor's algorithm, reducing integer factorization to an abelian HSP over the additive group of integers modulo N, has seen photonic and trapped-ion realizations for small N in the 2020s. Trapped-ion systems factored 15 (3×5) as early as 2001 but advanced to demonstrate the full procedure for N=15 and N=21 (3×7) with improved fidelities in recent years, using 5-7 qubits and achieving success rates up to 80% after post-selection. In 2024, a photonic implementation encoded Shor's algorithm in 32 time-bin dimensions of a single photon, successfully factoring 15 with a compiled circuit depth of 10, leveraging linear optics for high-dimensional state manipulation and attaining near-unity visibility in interference measurements.^[35] A landmark 2025 demonstration reported unconditional exponential quantum speedup for an abelian HSP variant— a low-weight Simon's problem—on a 127-qubit IBM superconducting processor, with error-corrected simulations scaling to effective group sizes where log |G| ≈ 10, outperforming classical solvers by factors exceeding 2^10 in runtime.^[36] While no full-scale Shor's implementation exists due to prohibitive error rates on current hardware, HSP primitives such as coset sampling and Fourier sampling have been tested in related NISQ benchmarks. Decoherence remains a primary challenge, limiting coherent coset state preparation times to microseconds and necessitating dynamical decoupling in all demonstrations.

Theoretical Generalizations

Recent theoretical advancements have extended the hidden subgroup problem (HSP) to infinite groups, revealing both hardness results and efficient solvability in specific cases. For the additive group of rational numbers \mathbb{Q}, the hidden subgroup existence problem—a decision variant of HSP—is NP-complete, establishing unconditional NP-hardness even with access to a quantum oracle for integer factoring via Shor's algorithm.^[37] In contrast, for finitely generated infinite abelian groups such as \mathbb{Z}^k, a quantum polynomial-time algorithm solves HSP with high probability, requiring query complexity polynomial in the dimension k and the bit length of the subgroup generators.^[37] These results highlight the nuanced complexity landscape for infinite settings, where structural properties like finite generation enable efficient quantum solutions, while denser structures like \mathbb{Q} resist polynomial-time resolution. The state hidden subgroup problem (StateHSP) generalizes HSP to oracles that output quantum states rather than classical values, providing a framework for problems involving hidden symmetries in quantum data. Introduced in 2025, StateHSP for abelian groups admits an efficient quantum algorithm that identifies the hidden stabilizer subgroup using O(\log |G|) queries, matching the query complexity of standard abelian HSP.^[38] This approach is particularly effective for locating unentanglement in multipartite quantum states, where the hidden subgroup corresponds to the stabilizer of separable subspaces, achieving success with probability approaching 1 in polynomial time.^[39] By leveraging quantum Fourier sampling over the group algebra, StateHSP bridges HSP with quantum state tomography, enabling applications in symmetry detection for noisy intermediate-scale quantum devices. To address practical overhead in quantum implementations, an initialization-free algorithm for general abelian HSP eliminates the need for ancillary qubits to prepare uniform superpositions over the group.^[40] This 2025 development constructs the required superposition directly from the HSP oracle using phase estimation techniques, reducing qubit requirements from O(\log |G|) ancillas to none while maintaining the standard O(\log |G|) query complexity and polynomial gate overhead.^[40] Such optimizations are crucial for resource-constrained quantum hardware, as they lower error accumulation from initialization circuits without compromising the algorithm's correctness. Quantum autoencoders incorporating HSP principles have advanced data compression for symmetric quantum datasets. In a 2024 framework, HSP-based autoencoders compress data hiding an abelian subgroup H \leq G using O(\log |G|) queries, achieving near-optimal compression rates for group-structured data, as proven via query complexity equivalence between HSP and the compression task, outperforming classical methods exponentially on instances like Simon's problem.^[41]

References

[1]
[PDF] The Hidden Subgroup Problem - arXiv
The Hidden Subgroup Problem is one of the most prominent topic in quantum computing. Most quantum algorithms running exponentially faster than their ...
[2]
[PDF] Lecture 10 -- The Hidden Subgroup Problem
Oct 12, 2015 · Definition 1.1. A coset of a subgroup H of a group G is the set {xh|h ∈ H} for some x ∈ G. This set ...<|control11|><|separator|>
[3]
Optimal measurements for the dihedral hidden subgroup problem
Jan 10, 2005 · Optimal measurements for the dihedral hidden subgroup problem. Authors:Dave Bacon, Andrew M. Childs, Wim van Dam.
[4]
https://arxiv.org/abs/2110.00827
[5]
The Hidden Subgroup Problem - Review and Open Problems - arXiv
Nov 4, 2004 · Abstract: An overview of quantum computing and in particular the Hidden Subgroup Problem are presented from a mathematical viewpoint.
[6]
[1008.0010] The Hidden Subgroup Problem - Quantum Physics - arXiv
Jul 30, 2010 · We give an overview of the Hidden Subgroup Problem (HSP) as of July 2010, including new results discovered since the survey of arXiv:quant-ph/0411037v1.
[7]
[PDF] a subexponential-time quantum algorithm for the dihedral hidden ...
The hidden subgroup problem (HSP) in quantum computa- tion takes as input a group G, a finite set S, and a black-box function (or oracle) f : G → S. By promise ...
[8]
[PDF] The quantum query complexity of the hidden subgroup ... - arXiv
A quantum algorithm can identify a hidden subgroup with a polynomial number of calls to the oracle, specifically O(log^4 |G|), for any finite group.
[9]
The Hidden Subgroup Problem and Quantum Computation Using ...
Abstract. The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed ...
[10]
[PDF] Math 120A — Introduction to Group Theory - UCI Mathematics
Definition 2.12 (Subgroup). Let G be a group. A subgroup of G is a non-empty subset H ⊆ G which remains a group with respect to the same binary operation. We ...
[11]
[PDF] 3 Basic concepts in group theory - 3.2 Subgroup - Xie Chen
(3) Any subgroup which is different from {e} and G is called a proper subgroup. Example: C2 = {e, b1} and C3 = {e, c, c2} are both proper subgroups of D3.
[12]
[PDF] Summary of Introductory Group Theory
Oct 28, 2024 · Thus, the cosets of a subgroup partition the group G. Also ... Then the quotient group G/N is the set of cosets of N with multiplication.
[13]
[PDF] quotient groups - keith conrad
3. Quotient Groups. By Theorem 2.11, we can meaningfully multiply cosets of a normal subgroup N of a group G by multiplying representatives for two cosets and ...Missing: basics | Show results with:basics
[14]
GroupTheory
7. Subgroups, cosets, and quotients. Let G be a group, and let H be a subgroup of G. For each element a of G, define Ha = { xa | x in H }.
[15]
[PDF] Orders of Abelian groups - Purdue Math
An abelian group A is called cyclic if there is an element a ∈ A (called a generator) such that every element of A is a power of A. For example Zn is cyclic ...Missing: definition ℤ_n (ℤ_p)^
[16]
[PDF] Finite Abelian Group Supplement - LSU Math
Define a group Epn by. Epn = Zp × Zp ืทททZp. (n factors). The group Epn is an abelian group of order pn with the property that every nonidentity element has ...Missing: ℤ_n (ℤ_p)^
[17]
[PDF] Notes on Representations of Finite Groups
Irreducible representations. We next introduce irreducible represen- tations, which are essentially the building blocks of representation theory. Definition 2.6 ...
[18]
[PDF] representation theory for finite groups - UChicago Math
Aug 29, 2014 · There are thus as many irreducible representations of a finite abelian group as there are elements of the group. For the non-abelian group ...
[19]
[PDF] Representation Theory - Berkeley Math
Every complex representation of a finite abelian group is completely re- ducible, and every irreducible representation is 1-dimensional. It will be our goal to ...
[20]
[PDF] Characters of finite abelian groups - Keith Conrad
The isomorphism between G and its double-dual group given by Pontryagin duality lets us think about every finite abelian group G as a dual group (namely the ...
[21]
Quantum Complexity Theory | SIAM Journal on Computing
Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem ... Solving Bernstein and Vazirani's Problem with the 2-bit Permutation ...
[22]
Quantum factoring, discrete logarithms and the hidden subgroup ...
Dec 17, 2000 · Finally we consider the non-abelian hidden subgroup problem mentioning some open questions where future quantum algorithms may be expected to ...
[23]
https://arxiv.org/pdf/quant-ph/0411037.pdf
[24]
The Quantum Fourier Transform and Extensions of the Abelian ...
Nov 30, 2002 · The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation.
[25]
[PDF] 1 Fourier Transform over Finite Abelian Groups - People @EECS
To define the Fourier transform, we consider the characters of G. A map χj : G → C is a character if it is a group. homomorphism, i.e. χj(gg0) = χj(g)χj(g0) ...
[26]
[PDF] LECTURE 3: The abelian hidden subgroup problem
In this lecture, we will introduce the general hidden subgroup problem (HSP). We'll see how Shor's discrete log algorithm solves a particular instance of the ...
[27]
On the Power of Quantum Computation - SIAM Publications Library
Daniel Simon, On the power of quantum computation, IEEE Comput. Soc. Press ... AbstractPDF (643 KB). View Options. View options. PDF. View PDF. Figures. Tables ...
[28]
Optimal Separation in Exact Query Complexities for Simon's Problem
Oct 6, 2016 · In particular, we show that Simon's problem can be solved by a classical deterministic algorithm with O(\sqrt{2^{n}}) queries (as we are aware, ...
[29]
Algorithms for quantum computation: discrete logarithms and factoring
This paper presents Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer, which are hard on classical computers.
[30]
[PDF] Quantum Me hani al Algorithms for the Nonabelian Hidden ...
It is natural to generalize the standard method for the abelian hidden subgroup problem to nonabelian groups. Fourier transforms over nonabelian groups are de ...Missing: formalized Bernstein
[31]
[2507.18499] The hidden subgroup problem for infinite groups - arXiv
Jul 24, 2025 · 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 ...
[32]
The State Hidden Subgroup Problem and an Efficient Algorithm for ...
Jun 15, 2025 · In this paper, we consider the hidden subgroup problem (HSP) over the class of semidirect product groups Zpr ⋊ Zq, for p and q prime. We first ...
[33]
The abelian state hidden subgroup problem - Quantum Physics - arXiv
May 21, 2025 · In this work, we investigate quantum learning problems in which the goal is to identify a hidden symmetry of an unknown quantum state.
[34]
An Initialization-free Quantum Algorithm for General Abelian Hidden ...
Jul 24, 2025 · Here we present an initialization-free quantum algorithm for solving HSP in the case where G is a finite abelian group.
[35]
Information compression via hidden subgroup quantum autoencoders
Aug 8, 2024 · We design a quantum method for classical information compression that exploits the hidden subgroup quantum algorithm.<|control11|><|separator|>