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

arXiv:2512.02087

A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective

Simone Dutto, Pietro Mercuri, Nadir Murru, Romano, Lorenzo

Published Dec 1, 2025• 0 citations
arXivHTMLPDF

Abstract

We provide a survey on the Hidden Subgroup Problem (HSP), which plays an important role in studying the security of public-key cryptosystems. We first review the abelian case, where Kitaev's algorithm yields an efficient quantum solution to the HSP, recalling how classical problems (such as order finding, integer factorization, and discrete logarithm) can be formulated as abelian HSP instances. We then examine the current state of the art for non-abelian HSP, where no general efficient quantum solution is known, focusing on some relevant groups including dihedral group (connected to the shortest vector problem), symmetric groups (connected to the graph isomorphism problem), and semidirect product constructions (connected, in a special case, to the code equivalence problem). We also describe the main techniques for addressing the HSP in non-abelian cases, namely Fourier sampling and the black-box approach. Throughout the paper, we highlight the mathematical notions required and exploited in this context, providing a cryptography-oriented perspective.

DOI
10.48550/arxiv.2512.02087

Related papers

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, Tharso D. Fernandes, Carlos Magno Martins Cosme

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 $\Z_{N}\rtimes\Z_{q^s}$ where $N$ is an integer with a special prime factorization, $q$ prime number and $s$ any positive integer.

TEMA (São Carlos)•Aug 24, 2017•7 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

The Hidden Subgroup Problem for Universal Algebras

Matthew Moore, Taylor Walenczyk

The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no polynomial-time solution for general groups has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, or classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.

arXiv:2001.11298•ACM/IEEE Symposium on Logic in Computer Science (LICS)•May 26, 2020•0 citations

The dihedral hidden subgroup problem

Imin Chen, David I. Sun

Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.

arXiv:2106.09907•Journal of Mathematical Cryptology•Jan 1, 2024•0 citations

Fully graphical treatment of the quantum algorithm for the Hidden Subgroup Problem

Stefano Gogioso, Kissinger, Aleks

The abelian Hidden Subgroup Problem (HSP) is extremely general, and many problems with known quantum exponential speed-up (such as integers factorisation, the discrete logarithm and Simon's problem) can be seen as specific instances of it. The traditional presentation of the quantum protocol for the abelian HSP is low-level, and relies heavily on the the interplay between classical group theory and complex vector spaces. Instead, we give a high-level diagrammatic presentation which showcases the quantum structures truly at play. Specifically, we provide the first fully diagrammatic proof of correctness for the abelian HSP protocol, showing that strongly complementary observables are the key ingredient to its success. Being fully diagrammatic, our proof extends beyond the traditional case of finite-dimensional quantum theory: for example, we can use it to show that Simon's problem can be efficiently solved in real quantum theory, and to obtain a protocol that solves the HSP for certain infinite abelian groups.

arXiv:1701.08669•Jan 30, 2017•7 citations
We provide a survey on the Hidden Subgroup Problem (HSP), which plays an important role in studying the security of public-key cryptosystems. We first review the abelian case, where Kitaev's algorithm yields an efficient quantum solution to the HSP, recalling how classical problems (such as order finding, integer factorization, and discrete logarithm) can be formulated as abelian HSP instances. We then examine the current state of the art for non-abelian HSP, where no general efficient quantum solution is known, focusing on some relevant groups including dihedral group (connected to the shortest vector problem), symmetric groups (connected to the graph isomorphism problem), and semidirect product constructions (connected, in a special case, to the code equivalence problem). We also describe the main techniques for addressing the HSP in non-abelian cases, namely Fourier sampling and the black-box approach. Throughout the paper, we highlight the mathematical notions required and exploited in this context, providing a cryptography-oriented perspective.
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) 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⋊Zqs\Z_{N}\rtimes\Z_{q^s}ZN​⋊Zqs​ where NNN is an integer with a special prime factorization, qqq prime number and sss any positive integer.
The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no polynomial-time solution for general groups has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, or classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.
Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.
The abelian Hidden Subgroup Problem (HSP) is extremely general, and many problems with known quantum exponential speed-up (such as integers factorisation, the discrete logarithm and Simon's problem) can be seen as specific instances of it. The traditional presentation of the quantum protocol for the abelian HSP is low-level, and relies heavily on the the interplay between classical group theory and complex vector spaces. Instead, we give a high-level diagrammatic presentation which showcases the quantum structures truly at play. Specifically, we provide the first fully diagrammatic proof of correctness for the abelian HSP protocol, showing that strongly complementary observables are the key ingredient to its success. Being fully diagrammatic, our proof extends beyond the traditional case of finite-dimensional quantum theory: for example, we can use it to show that Simon's problem can be efficiently solved in real quantum theory, and to obtain a protocol that solves the HSP for certain infinite abelian groups.