Metraipolis › archive › dc_7bda34235291
Quantum Algorithms for Minimum Generating Set — arXiv:2609.40260
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.40260
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:18:03.768Z
- SHA-256 of the archived text
1d8c7c05c656f6e1ef5273b0a77dfd7cb79df659757971e61af222bd66cb8b92- Stable URL of this page
https://metraipolis.com/documento/dc_7bda34235291
How to cite
Quantum Algorithms for Minimum Generating Set — arXiv:2609.40260 — arXiv (en), https://arxiv.org/abs/2609.40260 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7bda34235291 (Metraipolis archive dc_7bda34235291, sha256 1d8c7c05c656f6e1ef5273b0a77dfd7cb79df659757971e61af222bd66cb8b92)
BibTeX
@misc{dc7bda34235291,
title = {Quantum Algorithms for Minimum Generating Set — arXiv:2609.40260},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.40260},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7bda34235291; sha256 1d8c7c05c656f6e1ef5273b0a77dfd7cb79df659757971e61af222bd66cb8b92},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40260. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\Gamma_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 $\Gamma_d$. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from $\Gamma_d$. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from $\Gamma_d$. Finally, we show that the minimum generating set problem for general black-box groups is in $\textrm{NP} \cap \textrm{coAM}$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Group Theory (math.GR).
Pagina del lavoro: https://arxiv.org/abs/2609.40260 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:51:27.486Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).