Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Hidden subgroup problem in quantum computing

Shuhong Gao, Prasit Limbupasiriporn

Published Jan 1, 2005• 0 citations
OpenAlex

Abstract

We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.

Related papers

The Hidden Subgroup Problem

Frédéric Wang

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. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.

arXiv:1008.0010•Jul 30, 2010•10 citations

Dihedral Hidden Subgroup Problem: A Survey

Hirotada Kobayashi, François Le Gall

After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.

IPSJ Digital Courier•Jan 1, 2005•7 citations

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

Mauro E. S. Morales

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).

quant-pharXiv:2608.05321•Aug 7, 2026•0 citations

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over some Non-Abelian Groups

Demerson Nunes Gonçalves, Renato Portugal, Tharso D. Fernandes

The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms are special cases of the HSP. In this paper we show that there exist a new efficient quantum algorithm for the HSP on groups ZN o Zqs where N is an integer with a special prime factorization.

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics•Nov 18, 2015•0 citations

Quantum fourier sampling, the hidden subgroup problem, and beyond

Sean Hallgren, Umesh V. Vazirani

The Hidden Subgroup Problem (HSP) provides the fundamental framework for most quantum algorithms. Until very recently, all known problems where quantum computation provides a super-polynomial speedup over classical algorithms have been variants of the HSP for particular abelian groups. Examples include factoring integers and computing the discrete log, for which Shor found efficient quantum algorithms. The algorithm for these problems may be viewed as consisting of the main HSP solution plus an ad hoc method of dealing with the particular variant. In this dissertation, we give a systematic way of dealing with all these variants. The key component of our solution is a new theorem about the robustness of Fourier sampling. The purpose of this theorem is to better understand the structure underlying existing algorithms as well as to provide an algorithmic tool for the construction of future quantum algorithms. In addition, we also derive a new algorithm for computing the quantum Fourier transform which is asymptotically faster than any previously known algorithm. By contrast, the nonabelian HSP is wide open. It includes as a special case the longstanding open question of graph isomorphism, where the group is the symmetric group, S n . It is natural to carry over the abelian HSP algorithm to the nonabelian case. We show that in the case that the hidden subgroup is normal, this algorithm succeeds in reconstructing the subgroup in polynomial time. On the other hand, we give evidence that this algorithm is inadequate to even distinguish a trivial subgroup from an involution in t...

•Jan 1, 2000•4 citations

Quantum solution to the hidden subgroup problem for Poly-Near-Hamiltonian groups

Dmitry Gavinsky

The Hidden Subgroup Problem (HSP) has been widely studied in the context of quantum computing and is known to be efficiently solvable for Abelian groups, yet appears to be difficult for many non-Abelian ones. An efficient algorithm for the HSP over a group \f G\ runs in time polynomial in \f{n\deq\log|G|.} For any subgroup \f H\ of \f G, let \f{N(H)} denote the normalizer of \f H. Let \MG\ denote the intersection of all normalizers in \f G (i.e., \f{\MG=\cap_{H\leq G}N(H)}). \MG\ is always a subgroup of \f G and the index \f{[G:\MG]} can be taken as a measure of ``how non-Abelian'' \f G is (\f{[G:\MG] = 1} for Abelian groups). This measure was considered by Grigni, Schulman, Vazirani and Vazirani, who showed that whenever \f{[G:\MG]\in\exp(O(\log^{1/2}n))} the corresponding HSP can be solved efficiently (under certain assumptions). We show that whenever \f{[G:\MG]\in\poly(n)} the corresponding HSP can be solved efficiently, under the same assumptions (actually, we solve a slightly more general case of the HSP and also show that some assumptions may be relaxed).

Quantum Information and Computation•May 1, 2004•28 citations
We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups.
We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture.
For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem.
In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.
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. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.
After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.
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⋊φZpkG=A\rtimes_{\varphi} \mathbb{Z}_{p^k}G=A⋊φ​Zpk​, with AAA finite Abelian, ppp prime, k∈Nk\in \mathbb{N}k∈N and the action of Zpk\mathbb Z_{p^k}Zpk​ is generated by the scalar automorphism a↦μaa\mapstoμaa↦μa, for some μ∈ZExp⁡(A)×μ\in\mathbb Z_{\operatorname{Exp}(A)}^\timesμ∈ZExp(A)×​, where Exp(A)\mathrm{Exp}(A)Exp(A) is the exponent of AAA. Our algorithm is efficient when AAA has bounded generator rank and Exp(A)/p=polylog(∣G∣)\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)Exp(A)/p=polylog(∣G∣). This includes the case A=ZNA=\mathbb{Z}_NA=ZN​ for N∈NN\in\mathbb{N}N∈N and k=1k=1k=1, studied by Bacon, Childs and van Dam (FOCS 2005), and A=ZqrA=\mathbb{Z}_{q^r}A=Zqr​ with qqq prime and r∈Nr\in \mathbb{N}r∈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).
The Hidden Subgroup Problem (HSP) provides the fundamental framework for most quantum algorithms. Until very recently, all known problems where quantum computation provides a super-polynomial speedup over classical algorithms have been variants of the HSP for particular abelian groups. Examples include factoring integers and computing the discrete log, for which Shor found efficient quantum algorithms. The algorithm for these problems may be viewed as consisting of the main HSP solution plus an ad hoc method of dealing with the particular variant. In this dissertation, we give a systematic way of dealing with all these variants. The key component of our solution is a new theorem about the robustness of Fourier sampling. The purpose of this theorem is to better understand the structure underlying existing algorithms as well as to provide an algorithmic tool for the construction of future quantum algorithms. In addition, we also derive a new algorithm for computing the quantum Fourier transform which is asymptotically faster than any previously known algorithm. By contrast, the nonabelian HSP is wide open. It includes as a special case the longstanding open question of graph isomorphism, where the group is the symmetric group, S n . It is natural to carry over the abelian HSP algorithm to the nonabelian case. We show that in the case that the hidden subgroup is normal, this algorithm succeeds in reconstructing the subgroup in polynomial time. On the other hand, we give evidence that this algorithm is inadequate to even distinguish a trivial subgroup from an involution in t...
The Hidden Subgroup Problem (HSP) has been widely studied in the context of quantum computing and is known to be efficiently solvable for Abelian groups, yet appears to be difficult for many non-Abelian ones. An efficient algorithm for the HSP over a group \f G\ runs in time polynomial in \f{n\deq\log|G|.} For any subgroup \f H\ of \f G, let \f{N(H)} denote the normalizer of \f H. Let \MG\ denote the intersection of all normalizers in \f G (i.e., \f{\MG=\cap_{H\leq G}N(H)}). \MG\ is always a subgroup of \f G and the index \f{[G:\MG]} can be taken as a measure of ``how non-Abelian'' \f G is (\f{[G:\MG] = 1} for Abelian groups). This measure was considered by Grigni, Schulman, Vazirani and Vazirani, who showed that whenever \f{[G:\MG]\in\exp(O(\log^{1/2}n))} the corresponding HSP can be solved efficiently (under certain assumptions). We show that whenever \f{[G:\MG]\in\poly(n)} the corresponding HSP can be solved efficiently, under the same assumptions (actually, we solve a slightly more general case of the HSP and also show that some assumptions may be relaxed).