arXiv:2609.40260
Quantum Algorithms for Minimum Generating Set
Bireswar Das, Udit Kumar, Kavita Samant, Dhara Thakkar
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$.
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.