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:2609.40260

Quantum Algorithms for Minimum Generating Set

Bireswar Das, Udit Kumar, Kavita Samant, Dhara Thakkar

quant-phcs.CCmath.GRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

In this paper, we present a polynomial-time quantum algorithm for computing a minimum-sized generating set of solvable black-box groups. Next, we consider the class $Γ_d$ of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group $S_d$ for a fixed $d$. We design polynomial-time quantum algorithms to compute the direct product decomposition of abelian factor groups and solve the constructive membership problem for factor groups of groups from $Γ_d$. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from $Γ_d$. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from $Γ_d$. Finally, we show that the minimum generating set problem for general black-box groups is in $\textrm{NP} \cap \textrm{coAM}$.

AI Summary

The paper studies computing $d(G)$, the minimum number of generators of a finite group, together with a generating set attaining it, when $G$ is specified by black-box generators. It gives polynomial-time quantum algorithms for solvable groups and, more generally, groups in $\Gamma_d$, whose nonabelian composition factors embed in $S_d$ for fixed $d$. The quantum algorithms assume unique encodings of group elements; the solvable-group algorithm also handles quotients $G/N$. For solvable groups, the algorithm recursively finds a minimal normal subgroup and lifts a minimum generating set from the quotient. Minimal normal subgroups are obtained by decomposing abelian sections of the derived series and finding irreducible invariant subspaces for the conjugation action. For $\Gamma_d$, the paper constructs uniform subgroup superpositions and uses them to extend quantum algorithms for constructive membership, abelian decomposition, and related tasks to quotient groups. These subroutines yield a chief series, along which generators are lifted using existing group-generation results. A successful random lift has probability at least $53/(90\log|G|)$ when the proposed size is correct; $O((\log|G|)^2)$ trials per stage give high overall success probability. For unrestricted black-box groups, the decision problem $d(G)\leq k$ is placed in $\mathrm{NP}\cap\mathrm{coAM}$ using straight-line-program certificates and an Arthur–Merlin protocol checking chief-series generation claims. No polynomial-time quantum algorithm is given for unrestricted groups. The $\Gamma_d$ algorithms have polynomial dependence on $d!$, so their stated efficiency requires fixed $d$.

Little sign of AI-generated textUnclear writingPossible error

Error found: The chief-series proof incorrectly takes the derived series of the potentially nonsolvable ambient group G instead of the solvable normal closure of H; using that normal closure, as the later recursive construction does, repairs the error.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum algorithms for solvable groups

John Watrous

In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. Our algorithm works in the setting of black-box groups, wherein none of these problems can be computed classically in polynomial time. As an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.

arXiv:quant-ph/0011023•ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•99 citations

Improved Quantum Algorithms for Black-Box Abelian Group Decomposition

Junrong Luo, Yinan Li, Francois Le Gall

Decomposing finite Abelian black-box groups into cyclic factors is a basic problem in quantum computation. We give a quantum algorithm for decomposing finite Abelian black-box groups by adapting the quantum sampling and classical lattice-reduction method of Regev's factoring algorithm. The algorithm computes an invariant-factor decomposition and corresponding cyclic generators with high probability. For a group G of order at most 2^n with unique encodings and reversible group-operation cost T_op = Omega(sqrt(n)), our algorithm uses O(sqrt(n)) quantum circuits, each with O~(n T_op) gates and executed at most O(n) times. For comparison, we consider the Cheung-Mosca algorithm, which decomposes the Sylow p-subgroups separately. We also consider the common-modulus implementation of the extended Cheung-Mosca algorithm. Our algorithm reduces the sum of the circuit gate counts from O~(n^2 T_op) to O~(n^(3/2) T_op). The total quantum time bound reduces from O~(n^3 T_op) to O~(n^(5/2) T_op), and the quantum space bound reduces from O(n^2) to O(n) qubits. The classical computation uses polynomially many bit operations and group-operation queries. These improvements rely on two technical ingredients. We prove that the integer relation lattices used in our algorithm admit, with high probability, integral bases whose vectors have Euclidean norm at most exp(O(sqrt(n))). We preserve the circuit-size advantage of Regev's algorithm for group decomposition by incorporating all O(n) sampled generators while keeping the lattice-reduction dimension at O(sqrt(n)).

quant-pharXiv:2609.36480•Sep 30, 2026•0 citations

Quantum algorithms for a set of group theoretic problems

Stephen Fenner, Yong Zhang

We study two group theoretic problems, GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, in the setting of black-box groups, where DOUBLE COSET MEMBERSHIP generalizes a set of problems, including GROUP MEMBERSHIP, GROUP FACTORIZATION, and COSET INTERSECTION. No polynomial-time classical algorithms are known for these problems. We show that for solvable groups, there exist efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also study the decision versions of STABILIZER and ORBIT COSET, which generalizes GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, respectively. We show that they reduce to ORBIT COSET under certain conditions. Finally, we show that DOUBLE COSET MEMBERSHIP and DOUBLE COSET NONMEMBERSHIP have zero knowledge proof systems.

arXiv:quant-ph/0408150•Aug 24, 2004•2 citations

An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem

François Le Gall

In this paper we consider the problem of testing whether two finite groups are isomorphic. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. Le Gall has constructed an efficient classical algorithm for a class of groups corresponding to one of the most natural ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group $A$ by a cyclic group $Z_m$ with the order of $A$ coprime with $m$. More precisely, the running time of that algorithm is almost linear in the order of the input groups. In this paper we present a quantum algorithm solving the same problem in time polynomial in the logarithm of the order of the input groups. This algorithm works in the black-box setting and is the first quantum algorithm solving instances of the nonabelian group isomorphism problem exponentially faster than the best known classical algorithms.

arXiv:1001.0608•Leibniz international proceedings in informatics•Jan 1, 2010•6 citations

Quantum Algorithms for a Set of Group Theoretic Problems

Stephen Fenner, Yong Zhang

We introduce two decision problems, STABILIZERD and TRANSLATING COSETD, and give quantum reductions from them to the problem ORBIT SUPERPOSITION, as well as quantum reductions to them from two group theoretic problems GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP. Based on these reductions, efficient quantum algorithms are obtained for GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP in the setting of black-box groups. Specifically, for solvable groups, this gives efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also show that GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP are in the complexity class SZK.

International Journal of Foundations of Computer Science•Feb 1, 2015•2 citations

Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups

Y. Inui, François Le Gall

In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_q$, for $p$ and $q$ prime. We first present a classification of these groups in five classes. Then, we describe a polynomial-time quantum algorithm solving the HSP over all the groups of one of these classes: the groups of the form $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_p$, where $p$ is an odd prime. Our algorithm works even in the most general case where the group is presented as a black-box group with not necessarily unique encoding. Finally, we extend this result and present an efficient algorithm solving the HSP over the groups $\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_p$.

arXiv:quant-ph/0412033•Quantum Information and Computation•Jul 1, 2007•24 citations
In this paper, we present a polynomial-time quantum algorithm for computing a minimum-sized generating set of solvable black-box groups. Next, we consider the class ΓdΓ_dΓd​ of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group SdS_dSd​ for a fixed ddd. We design polynomial-time quantum algorithms to compute the direct product decomposition of abelian factor groups and solve the constructive membership problem for factor groups of groups from ΓdΓ_dΓd​. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from ΓdΓ_dΓd​. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from ΓdΓ_dΓd​. Finally, we show that the minimum generating set problem for general black-box groups is in NP∩coAM\textrm{NP} \cap \textrm{coAM}NP∩coAM.
The paper studies computing d(G)d(G)d(G), the minimum number of generators of a finite group, together with a generating set attaining it, when GGG is specified by black-box generators. It gives polynomial-time quantum algorithms for solvable groups and, more generally, groups in Γd\Gamma_dΓd​, whose nonabelian composition factors embed in SdS_dSd​ for fixed ddd. The quantum algorithms assume unique encodings of group elements; the solvable-group algorithm also handles quotients G/NG/NG/N.
For solvable groups, the algorithm recursively finds a minimal normal subgroup and lifts a minimum generating set from the quotient. Minimal normal subgroups are obtained by decomposing abelian sections of the derived series and finding irreducible invariant subspaces for the conjugation action. For Γd\Gamma_dΓd​, the paper constructs uniform subgroup superpositions and uses them to extend quantum algorithms for constructive membership, abelian decomposition, and related tasks to quotient groups. These subroutines yield a chief series, along which generators are lifted using existing group-generation results. A successful random lift has probability at least 53/(90log⁡∣G∣)53/(90\log|G|)53/(90log∣G∣) when the proposed size is correct; O((log⁡∣G∣)2)O((\log|G|)^2)O((log∣G∣)2) trials per stage give high overall success probability.
For unrestricted black-box groups, the decision problem d(G)≤kd(G)\leq kd(G)≤k is placed in NP∩coAM\mathrm{NP}\cap\mathrm{coAM}NP∩coAM using straight-line-program certificates and an Arthur–Merlin protocol checking chief-series generation claims. No polynomial-time quantum algorithm is given for unrestricted groups. The Γd\Gamma_dΓd​ algorithms have polynomial dependence on d!d!d!, so their stated efficiency requires fixed ddd.
In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. Our algorithm works in the setting of black-box groups, wherein none of these problems can be computed classically in polynomial time. As an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.
Decomposing finite Abelian black-box groups into cyclic factors is a basic problem in quantum computation. We give a quantum algorithm for decomposing finite Abelian black-box groups by adapting the quantum sampling and classical lattice-reduction method of Regev's factoring algorithm. The algorithm computes an invariant-factor decomposition and corresponding cyclic generators with high probability. For a group G of order at most 2^n with unique encodings and reversible group-operation cost T_op = Omega(sqrt(n)), our algorithm uses O(sqrt(n)) quantum circuits, each with O~(n T_op) gates and executed at most O(n) times. For comparison, we consider the Cheung-Mosca algorithm, which decomposes the Sylow p-subgroups separately. We also consider the common-modulus implementation of the extended Cheung-Mosca algorithm. Our algorithm reduces the sum of the circuit gate counts from O~(n^2 T_op) to O~(n^(3/2) T_op). The total quantum time bound reduces from O~(n^3 T_op) to O~(n^(5/2) T_op), and the quantum space bound reduces from O(n^2) to O(n) qubits. The classical computation uses polynomially many bit operations and group-operation queries. These improvements rely on two technical ingredients. We prove that the integer relation lattices used in our algorithm admit, with high probability, integral bases whose vectors have Euclidean norm at most exp(O(sqrt(n))). We preserve the circuit-size advantage of Regev's algorithm for group decomposition by incorporating all O(n) sampled generators while keeping the lattice-reduction dimension at O(sqrt(n)).
We study two group theoretic problems, GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, in the setting of black-box groups, where DOUBLE COSET MEMBERSHIP generalizes a set of problems, including GROUP MEMBERSHIP, GROUP FACTORIZATION, and COSET INTERSECTION. No polynomial-time classical algorithms are known for these problems. We show that for solvable groups, there exist efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also study the decision versions of STABILIZER and ORBIT COSET, which generalizes GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, respectively. We show that they reduce to ORBIT COSET under certain conditions. Finally, we show that DOUBLE COSET MEMBERSHIP and DOUBLE COSET NONMEMBERSHIP have zero knowledge proof systems.
In this paper we consider the problem of testing whether two finite groups are isomorphic. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. Le Gall has constructed an efficient classical algorithm for a class of groups corresponding to one of the most natural ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group AAA by a cyclic group ZmZ_mZm​ with the order of AAA coprime with mmm. More precisely, the running time of that algorithm is almost linear in the order of the input groups. In this paper we present a quantum algorithm solving the same problem in time polynomial in the logarithm of the order of the input groups. This algorithm works in the black-box setting and is the first quantum algorithm solving instances of the nonabelian group isomorphism problem exponentially faster than the best known classical algorithms.
We introduce two decision problems, STABILIZERD and TRANSLATING COSETD, and give quantum reductions from them to the problem ORBIT SUPERPOSITION, as well as quantum reductions to them from two group theoretic problems GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP. Based on these reductions, efficient quantum algorithms are obtained for GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP in the setting of black-box groups. Specifically, for solvable groups, this gives efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also show that GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP are in the complexity class SZK.
In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups Zpr⋊Zq\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_qZpr​⋊Zq​, for ppp and qqq prime. We first present a classification of these groups in five classes. Then, we describe a polynomial-time quantum algorithm solving the HSP over all the groups of one of these classes: the groups of the form Zpr⋊Zp\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_pZpr​⋊Zp​, where ppp is an odd prime. Our algorithm works even in the most general case where the group is presented as a black-box group with not necessarily unique encoding. Finally, we extend this result and present an efficient algorithm solving the HSP over the groups Zprm⋊Zp\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_pZprm​⋊Zp​.