{"id":"arxiv/2609.36480","url":"https://arxiv.org/abs/2609.36480","tags":["quant-ph"],"score":0,"title":"Improved Quantum Algorithms for Black-Box Abelian Group Decomposition","domain":"quant-ph","source":"arxiv","authors":["Junrong Luo","Yinan Li","Francois Le Gall"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}