Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 44 min ago
PreprintCC BY 4.0arXiv

Quantum Algorithms for Minimum Generating Set

  • Bireswar Das
  • Udit Kumar
  • Kavita Samant
  • Dhara Thakkar
Open at sourcePDFDOICite

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 Sd 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 NP ∩ coAM.

Related

  1. Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with m+2 Edges
    Rostislav Klech
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  2. Counterexamples to additivity of minimum output p-Rényi entropy of quantum channels for all p≥ 0
    Debbie Leung, Benjamin Lovitz, Ion Nechita +1
    arXivPreprintCC BY 4.0Full textMathematical physicsProbabilityarXiv
  3. Quantum minimum description of density matrices
    Patrick Hayden, Alexander Maloney, Jinzhao Wang +1
    arXivPreprintCC BY 4.0Full textMathematical physicsQuantum physics & quantum informationarXiv
  4. Generating quantum error correcting codes from topological pre-thermal scars
    William N. Faugno, Frank Barrows, Terry A. Loring +2
    arXivPreprintCC BY 4.0Full textMathematical physicsAtomic, molecular & optical physicsarXiv
  5. Plotkin-optimal pure quantum LRCs with large minimum distances from NMDS codes
    Yang Li, Shitao Li, Gaojun Luo +1
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{das2026quantum,
  title = {{Quantum Algorithms for Minimum Generating Set}},
  author = {Bireswar Das and Udit Kumar and Kavita Samant and Dhara Thakkar},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40260},
  eprint = {2609.40260},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40260},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Quantum Algorithms for Minimum Generating Set
AU  - Bireswar Das
AU  - Udit Kumar
AU  - Kavita Samant
AU  - Dhara Thakkar
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40260
UR  - https://arxiv.org/abs/2609.40260
AB  - 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 NP ∩ coAM.
ER  -