arXiv:2609.36480
Improved Quantum Algorithms for Black-Box Abelian Group Decomposition
Junrong Luo, Yinan Li, Francois Le Gall
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)).
AI Summary
The paper asks whether Regev’s Gaussian Fourier-sampling and lattice-reduction approach can improve the quantum resources needed to decompose a finite Abelian black-box group. It gives an algorithm that outputs invariant factors and corresponding cyclic generators for $|G|\leq 2^n$, assuming unique $O(n)$-bit encodings and reversible group operations costing $T_{\mathrm{op}}=\Omega(\sqrt n)$ gates with $O(n)$ workspace. The algorithm uses $O(\sqrt n)$ circuits, each of size $\widetilde O(nT_{\mathrm{op}})$ and executed at most $O(n)$ times. Total quantum time is $\widetilde O(n^{5/2}T_{\mathrm{op}})$, quantum space is $O(n)$ qubits, and success probability is at least $1-O(n^{-3/2})$. The analyzed Cheung–Mosca and common-modulus extended Cheung–Mosca implementations instead have bounds of $\widetilde O(n^3T_{\mathrm{op}})$ quantum time and $O(n^2)$ qubits. The construction processes $O(n)$ sampled generators in batches of $O(\sqrt n)$. At each subgroup extension, known small-order cyclic factors are handled directly, while randomized combinations of large-order factors and new elements define an $O(\sqrt n)$-dimensional relation lattice. Character-sum estimates and geometry-of-numbers arguments establish, with high probability, an integral basis of length $\exp(O(\sqrt n))$. Joint cyclic and Gaussian Fourier sampling, LLL-based lattice recovery, exact character reconstruction, and Smith normal form then produce the updated decomposition. The bounds concern quantum resources; classical processing and group-operation queries are bounded only polynomially. Comparisons are against the specified implementations, not lower bounds. The guarantees rely on the encoding, sampling, and reversible-operation assumptions, and no concrete resource estimates are provided.
ChatGPT was also used to help correct minor errors in intermediate drafts, resolve inconsistencies in notation and references, and improve the language.
Central claim may not hold: The decomposition algorithm assumes independent uniform samples from G without supplying a sampler, initial generators, or a construction of those samples from the stated group-operation interface. The abstract's O(n)-qubit claim needs the body's additional assumptions of O(n)-bit element encodings and O(n) group-operation workspace, which do not follow from unique encoding and the group-order bound.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- Revised and streamlined the presentation in several sections; no changes to the main results or conclusions