Improved Quantum Algorithms for Black-Box Abelian Group Decomposition

Abstract

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)).

Improved Quantum Algorithms for Rényi Entropies Estimation
Zongxing Xiong, Chengshen Gao, Lvzhou Li
arXiv14 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
A novel deep learning prediction method for PM2.5 integrating improved MSTL decomposition and FATA optimization algorithm
Xiaoliang Zhao, Pinyuan Qiao, Bandna Bharti +5
PLOS One15 Sep 2026Peer-reviewedCC BY 4.0Full textEnvironmental science & pollution StatisticsPLOS
Beyond quasinormal modes: A complete mode decomposition of black hole perturbations
Paolo Arnaudo, Javier Carballo, Benjamin Withers
Physical review. D/Physical review. D.11 Jun 2026Peer-reviewedLicence not statedFull text32 citedHigh-energy & particle physicsOpenAlex
Black holes and Abelian instantons
Isabel Garcia Garcia, Elliot Maderazo
Journal of High Energy Physics2 Oct 2026Peer-reviewedCC BY 4.0Full text1 citedHigh-energy & particle physicsCrossref
Hadrons in 𝒩=2 supersymmetric QCD from non-Abelian string on 2D black hole
E. Ievlev, A. Marshakov, G. Sumbatian +1
arXiv29 Oct 2026PreprintarXiv licenceFull textHigh-energy & particle physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{luo2026improved,
  title = {{Improved Quantum Algorithms for Black-Box Abelian Group Decomposition}},
  author = {Junrong Luo and Yinan Li and Francois Le Gall},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.36480},
  eprint = {2609.36480},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.36480},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Improved Quantum Algorithms for Black-Box Abelian Group Decomposition
AU  - Junrong Luo
AU  - Yinan Li
AU  - Francois Le Gall
PY  - 2026
DA  - 2026/10/04
PB  - arXiv
DO  - 10.48550/arxiv.2609.36480
UR  - https://arxiv.org/abs/2609.36480
AB  - 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)).
ER  -

Abstract

Related

Cite