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

Computer Science Research Notes

Introducing the hidden subgroup problem in discrete mathematics class

Se Hee Kim, Jiwoo Seo, Minju Kim, Yerak Kim, Seohyeon Baek, Seongbin Park

Published Jan 1, 2025• 0 citations
Publisher

Abstract

Discrete mathematics is a branch of mathematics that deals with discrete structures, where a discrete structure is defined as either a finite nonempty set or a countably infinite set over which various relations, operations are defined.For computer science students, this is a class where fundamental subjects such as logic, number theory, relation, set theory, graph theory, algorithms are introduced in such a way that these subjects can be understood without much mathematics [Sandefur22].In this poster, we describe our ongoing research that aims to introduce quantum computing to students without technical backgrounds[Jkim23, Slee23, Sjeong24].More specifically, we argue that the hidden subgroup problem[Hallgren03] is a good subject that can be taught in discrete mathematics class because the problem deals with a simple discrete structure that can be easily explained to the students of discrete mathematics class.In addition, since it is well known that the famous quantum algorithms such as Simon's algorithm and Shor's algorithm solve the instances of the hidden subgroup problem[Nielsen16], we believe that introduction to the hidden subgroup problem can help students gain insights into the structural properties of computational problems in a wide perspective.

DOI
10.24132/csrn.2025-a59

Related papers

The Hidden Subgroup Problem and Quantum Computation Using Group Representations

Sean Hallgren, Alexander C. Russell, Amnon Ta‐Shma

The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.

SIAM Journal on Computing•Jan 1, 2003•105 citations

Efficient Quantum Algorithms (In German: Effiziente Quantenalgorithmen)

Andreas Klappenecker, Martin Roetteler

Ever since the discovery of efficient quantum algorithms for factoring and computing discrete logarithms by Shor in 1994, the interest in quantum algorithms was growing within the theoretical computer science as well as the physics community. Surprisingly, the number of quantum algorithms found so far is quite small, although the number of researchers working on the subject is rapidly increasing. In fact, the task of designing new quantum algorithms has been proven to be extremely difficult. We give an overview of the problems for which an efficient quantum algorithm is known and briefly describe the underlying ideas. One large area of problems where a quantum computer appears to be superior to classical computers are the so-called hidden subgroup problems. We explain the relevance and the motivation behind this abstract class of problems.

•Jan 1, 2006•0 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

Quantum Hidden Subgroup Problems: A Mathematical Perspective

Samuel J. Lomonaco, Louis Hirsch Kauffman

The ultimate objective of this paper is to create a stepping stone to the development of new quantum algorithms. The strategy chosen is to begin by focusing on the class of abelian quantum hidden subgroup algorithms, i.e., the class of abelian algorithms of the Shor/Simon genre. Our strategy is to make this class of algorithms as mathematically transparent as possible. By the phrase "mathematically transparent" we mean to expose, to bring to the surface, and to make explicit the concealed mathematical structures that are inherently and fundamentally a part of such algorithms. In so doing, we create symbolic abelian quantum hidden subgroup algorithms that are analogous to the those symbolic algorithms found within such software packages as Axiom, Cayley, Maple, Mathematica, and Magma. As a spin-off of this effort, we create three different generalizations of Shor's quantum factoring algorithm to free abelian groups of finite rank. We refer to these algorithms as wandering (or vintage Z_Q) Shor algorithms. They are essentially quantum algorithms on free abelian groups A of finite rank n which, with each iteration, first select a random cyclic direct summand Z of the group A and then apply one iteration of the standard Shor algorithm to produce a random character of the "approximating" finite group A=Z_Q, called the group probe. These characters are then in turn used to find either the order P of a maximal cyclic subgroup Z_P of the hidden quotient group H_phi, or the entire hidden quotient group H_phi. An integral part of these wandering quantum algorithms is the selection of a very special random transversal, which we refer to as a Shor transversal. The algorithmic time complexity of the first of these wandering Shor algorithms is found to be O(n^2(lgQ)^3(lglgQ)^(n+1)).

arXiv:quant-ph/0201095•Jan 22, 2002•14 citations

Hidden Subhypergroup Problem

Massoud Amini, Mehrdad Kalantar, Mahmood M. Roozbehani

The Hidden Subgroup Problem is used in many quantum algorithms such as Simon's algorithm and Shor's factoring and discrete log algorithms. A polynomial time solution is known in case of abelian groups, and normal subgroups of arbitrary finite groups. The general case is still open. An efficient solution of the problem for symmetric group $S_n$ would give rise to an efficient quantum algorithm for Graph Isomorphism Problem. We formulate a hidden sub-hypergroup problem for finite hypergroups and solve it for finite commutative hypergroups. The given algorithm is efficient if the corresponding QFT could be calculated efficiently.

arXiv:quant-ph/0609220•Sep 28, 2006•4 citations

Normal subgroup reconstruction and quantum computation using group representations

Sean Hallgren, Alexander C. Russell, Amnon Ta‐Shma

The Hidden Subgroup Problem is the foundation of many quantum algorithms.An efficient solution is known for the problem over Abelian groups and this was used in Simon's algorithm and Shor's Factoring and Discrete Log algorithms.The non-Abelian case is open; an efficient solution would give rise to an efficient quantum algorithm for Graph Isomorphism.We fully analyze a natural generalization of the Abelian case solution to the non-Abelian case, and give an efficient solution to the problem for normal subgroups.We show, however, that this immediate generalization of the Abelian algorithm does not efficiently solve Graph Isomorphism.

ACM Symposium on Theory of Computing (STOC)•May 1, 2000•112 citations
Discrete mathematics is a branch of mathematics that deals with discrete structures, where a discrete structure is defined as either a finite nonempty set or a countably infinite set over which various relations, operations are defined.For computer science students, this is a class where fundamental subjects such as logic, number theory, relation, set theory, graph theory, algorithms are introduced in such a way that these subjects can be understood without much mathematics [Sandefur22].In this poster, we describe our ongoing research that aims to introduce quantum computing to students without technical backgrounds[Jkim23, Slee23, Sjeong24].More specifically, we argue that the hidden subgroup problem[Hallgren03] is a good subject that can be taught in discrete mathematics class because the problem deals with a simple discrete structure that can be easily explained to the students of discrete mathematics class.In addition, since it is well known that the famous quantum algorithms such as Simon's algorithm and Shor's algorithm solve the instances of the hidden subgroup problem[Nielsen16], we believe that introduction to the hidden subgroup problem can help students gain insights into the structural properties of computational problems in a wide perspective.
The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.
Ever since the discovery of efficient quantum algorithms for factoring and computing discrete logarithms by Shor in 1994, the interest in quantum algorithms was growing within the theoretical computer science as well as the physics community. Surprisingly, the number of quantum algorithms found so far is quite small, although the number of researchers working on the subject is rapidly increasing. In fact, the task of designing new quantum algorithms has been proven to be extremely difficult. We give an overview of the problems for which an efficient quantum algorithm is known and briefly describe the underlying ideas. One large area of problems where a quantum computer appears to be superior to classical computers are the so-called hidden subgroup problems. We explain the relevance and the motivation behind this abstract class of problems.
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 ultimate objective of this paper is to create a stepping stone to the development of new quantum algorithms. The strategy chosen is to begin by focusing on the class of abelian quantum hidden subgroup algorithms, i.e., the class of abelian algorithms of the Shor/Simon genre. Our strategy is to make this class of algorithms as mathematically transparent as possible. By the phrase "mathematically transparent" we mean to expose, to bring to the surface, and to make explicit the concealed mathematical structures that are inherently and fundamentally a part of such algorithms. In so doing, we create symbolic abelian quantum hidden subgroup algorithms that are analogous to the those symbolic algorithms found within such software packages as Axiom, Cayley, Maple, Mathematica, and Magma. As a spin-off of this effort, we create three different generalizations of Shor's quantum factoring algorithm to free abelian groups of finite rank. We refer to these algorithms as wandering (or vintage Z_Q) Shor algorithms. They are essentially quantum algorithms on free abelian groups A of finite rank n which, with each iteration, first select a random cyclic direct summand Z of the group A and then apply one iteration of the standard Shor algorithm to produce a random character of the "approximating" finite group A=Z_Q, called the group probe. These characters are then in turn used to find either the order P of a maximal cyclic subgroup Z_P of the hidden quotient group H_phi, or the entire hidden quotient group H_phi. An integral part of these wandering quantum algorithms is the selection of a very special random transversal, which we refer to as a Shor transversal. The algorithmic time complexity of the first of these wandering Shor algorithms is found to be O(n^2(lgQ)^3(lglgQ)^(n+1)).
The Hidden Subgroup Problem is used in many quantum algorithms such as Simon's algorithm and Shor's factoring and discrete log algorithms. A polynomial time solution is known in case of abelian groups, and normal subgroups of arbitrary finite groups. The general case is still open. An efficient solution of the problem for symmetric group SnS_nSn​ would give rise to an efficient quantum algorithm for Graph Isomorphism Problem. We formulate a hidden sub-hypergroup problem for finite hypergroups and solve it for finite commutative hypergroups. The given algorithm is efficient if the corresponding QFT could be calculated efficiently.
The Hidden Subgroup Problem is the foundation of many quantum algorithms.An efficient solution is known for the problem over Abelian groups and this was used in Simon's algorithm and Shor's Factoring and Discrete Log algorithms.The non-Abelian case is open; an efficient solution would give rise to an efficient quantum algorithm for Graph Isomorphism.We fully analyze a natural generalization of the Abelian case solution to the non-Abelian case, and give an efficient solution to the problem for normal subgroups.We show, however, that this immediate generalization of the Abelian algorithm does not efficiently solve Graph Isomorphism.