Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.36480

Improved Quantum Algorithms for Black-Box Abelian Group Decomposition

Junrong Luo, Yinan Li, Francois Le Gall

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations• Revised Oct 4, 2026 (v2)
v1 · Sep 29, 2026v2 · Oct 4, 2026
arXivHTMLPDF

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.

Little sign of AI-generated textAI use disclosed
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

Related papers

The computational power of normalizer circuits over black-box groups

Juan Bermejo-Vega, Cedric Yen-Yu Lin, Maarten Van den Nest

This work presents a precise connection between Clifford circuits, Shor's factoring algorithm and several other famous quantum algorithms with exponential quantum speed-ups for solving Abelian hidden subgroup problems. We show that all these different forms of quantum computation belong to a common new restricted model of quantum operations that we call \emph{black-box normalizer circuits}. To define these, we extend the previous model of normalizer circuits [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], which are built of quantum Fourier transforms, group automorphism and quadratic phase gates associated to an Abelian group $G$. In previous works, the group $G$ is always given in an explicitly decomposed form. In our model, we remove this assumption and allow $G$ to be a black-box group. While standard normalizer circuits were shown to be efficiently classically simulable [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], we find that normalizer circuits are powerful enough to factorize and solve classically-hard problems in the black-box setting. We further set upper limits to their computational power by showing that decomposing finite Abelian groups is complete for the associated complexity class. In particular, solving this problem renders black-box normalizer circuits efficiently classically simulable by exploiting the generalized stabilizer formalism in [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208]. Lastly, we employ our connection to draw a few practical implications for quantum algorithm design: namely, we give a no-go theorem for finding new quantum algorithms with black-box normalizer circuits, a universality result for low-depth normalizer circuits, and identify two other complete problems.

arXiv:1409.4800•Sep 16, 2014•10 citations

Quantum Algorithms for Minimum Generating Set

Bireswar Das, Udit Kumar, Kavita Samant +1 more

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 $\textrm{NP} \cap \textrm{coAM}$.

quant-pharXiv:2609.40260•Oct 1, 2026•0 citations

Alternative models for quantum computation

Cedric Yen-Yu Lin

We propose and study two new computational models for quantum computation, and infer new insights about the circumstances that give quantum computers an advantage over classical ones. The bomb query complexity model is a variation on the query complexity model, inspired by the Elitzur-Vaidman bomb tester. In this model after each query to the black box the result is measured, and the algorithm fails if the measurement gives a 1. We show that the bomb query complexity is asymptotically the square of the usual quantum query complexity. We then show a general method of converting certain classical algorithms to bomb query algorithms, which then give improved quantum algorithms. We apply this general method to graph problems, giving improved quantum query algorithms for single-source shortest paths and maximum bipartite matching. Normalizer circuits are a class of restricted quantum circuits defined on Hilbert spaces associated with Abelian groups. These circuits generalize the Clifford group, and are composed of gates implementing quantum Fourier transforms, automorphisms, and quadratic phases. We show that these circuits can be simulated efficiently on a classical computer even on infinite Abelian groups (the finite case is known [1, 21), as long as the group is decomposed into primitive subgroups. This result gives a generalization of the Gottesman-Knill theorem to infinite groups. However, if the underlying group is not decomposed (the group is a black box group) then normalizer circuits include many well known quantum algorithms, including Shor's factoring algorithm. There is therefore a large difference in computational power between normalizer circuits over explicitly decomposed versus black box groups. In fact, we show that a version of the problem of decomposing Abelian groups is complete for the complexity class associated with normalizer circuits over black box groups: any such normalizer circuit can be simulated classically given the ability to decompose Abelian groups.

•Jan 1, 2015•0 citations

Decomposing finite Abelian groups

Ka Chun Cheung, Michele Mosca

This paper describes a quantum algorithm for efficiently decomposing finite Abelian groups into a product of cyclic groups. Such a decomposition is needed in order to apply the Abelian hidden subgroup algorithm. Such a decomposition (assuming the Generalized Riemann Hypothesis) also leads to an efficient algorithm for computing class numbers (known to be at least as difficult as factoring).

arXiv:cs/0101004•Quantum Information and Computation•Oct 1, 2001•30 citations

The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem

Lisa Hales

The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.

arXiv:quant-ph/0212002•Nov 30, 2002•28 citations

Space-Optimized and Experimental Implementations of Regev's Quantum Factoring Algorithm

Wentao Yang, Bao Yan, Muxi Zheng +3 more

The integer factorization problem (IFP) underpins the security of RSA, yet becomes efficiently solvable on a quantum computer through Shor's algorithm. Regev's recent high-dimensional variant reduces the circuit size through lattice-based post-processing, but introduces substantial space overhead and lacks practical implementations. Here, we propose a qubit reuse method by intermediate-uncomputation that significantly reduces the space complexity of Regev's algorithm, inspired by reversible computing. Our basic strategy lowers the cost from \( O(n^{3/2}) \) to \( O(n^{5/4}) \), and refined strategies achieve \( O(n \log n) \)which is a space lower bound within this model. Simulations demonstrate the resulting time-space trade-offs and resource scaling. Moreover, we construct and compile quantum circuits that factor \( N = 35 \), verifying the effectiveness of our method through noisy simulations. A more simplified experimental circuit for Regev's algorithm is executed on a superconducting quantum computer, with lattice-based post-processing successfully retrieving the factors. These results advance the practical feasibility of Regev-style quantum factoring and provide guidance for future theoretical and experimental developments.

quant-pharXiv:2511.18198•Nov 25, 2025•0 citations
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)).
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∣≤2n|G|\leq 2^n∣G∣≤2n, assuming unique O(n)O(n)O(n)-bit encodings and reversible group operations costing Top=Ω(n)T_{\mathrm{op}}=\Omega(\sqrt n)Top​=Ω(n​) gates with O(n)O(n)O(n) workspace.
The algorithm uses O(n)O(\sqrt n)O(n​) circuits, each of size O~(nTop)\widetilde O(nT_{\mathrm{op}})O(nTop​) and executed at most O(n)O(n)O(n) times. Total quantum time is O~(n5/2Top)\widetilde O(n^{5/2}T_{\mathrm{op}})O(n5/2Top​), quantum space is O(n)O(n)O(n) qubits, and success probability is at least 1−O(n−3/2)1-O(n^{-3/2})1−O(n−3/2). The analyzed Cheung–Mosca and common-modulus extended Cheung–Mosca implementations instead have bounds of O~(n3Top)\widetilde O(n^3T_{\mathrm{op}})O(n3Top​) quantum time and O(n2)O(n^2)O(n2) qubits.
The construction processes O(n)O(n)O(n) sampled generators in batches of O(n)O(\sqrt n)O(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(n)O(\sqrt n)O(n​)-dimensional relation lattice. Character-sum estimates and geometry-of-numbers arguments establish, with high probability, an integral basis of length exp⁡(O(n))\exp(O(\sqrt n))exp(O(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.
This work presents a precise connection between Clifford circuits, Shor's factoring algorithm and several other famous quantum algorithms with exponential quantum speed-ups for solving Abelian hidden subgroup problems. We show that all these different forms of quantum computation belong to a common new restricted model of quantum operations that we call \emph{black-box normalizer circuits}. To define these, we extend the previous model of normalizer circuits [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], which are built of quantum Fourier transforms, group automorphism and quadratic phase gates associated to an Abelian group GGG. In previous works, the group GGG is always given in an explicitly decomposed form. In our model, we remove this assumption and allow GGG to be a black-box group. While standard normalizer circuits were shown to be efficiently classically simulable [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], we find that normalizer circuits are powerful enough to factorize and solve classically-hard problems in the black-box setting. We further set upper limits to their computational power by showing that decomposing finite Abelian groups is complete for the associated complexity class. In particular, solving this problem renders black-box normalizer circuits efficiently classically simulable by exploiting the generalized stabilizer formalism in [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208]. Lastly, we employ our connection to draw a few practical implications for quantum algorithm design: namely, we give a no-go theorem for finding new quantum algorithms with black-box normalizer circuits, a universality result for low-depth normalizer circuits, and identify two other complete problems.
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Γ_dΓd​ of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group SdS_dSd​ for a fixed ddd. 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Γ_dΓd​. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from ΓdΓ_dΓd​. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from ΓdΓ_dΓd​. Finally, we show that the minimum generating set problem for general black-box groups is in NP∩coAM\textrm{NP} \cap \textrm{coAM}NP∩coAM.
We propose and study two new computational models for quantum computation, and infer new insights about the circumstances that give quantum computers an advantage over classical ones. The bomb query complexity model is a variation on the query complexity model, inspired by the Elitzur-Vaidman bomb tester. In this model after each query to the black box the result is measured, and the algorithm fails if the measurement gives a 1. We show that the bomb query complexity is asymptotically the square of the usual quantum query complexity. We then show a general method of converting certain classical algorithms to bomb query algorithms, which then give improved quantum algorithms. We apply this general method to graph problems, giving improved quantum query algorithms for single-source shortest paths and maximum bipartite matching. Normalizer circuits are a class of restricted quantum circuits defined on Hilbert spaces associated with Abelian groups. These circuits generalize the Clifford group, and are composed of gates implementing quantum Fourier transforms, automorphisms, and quadratic phases. We show that these circuits can be simulated efficiently on a classical computer even on infinite Abelian groups (the finite case is known [1, 21), as long as the group is decomposed into primitive subgroups. This result gives a generalization of the Gottesman-Knill theorem to infinite groups. However, if the underlying group is not decomposed (the group is a black box group) then normalizer circuits include many well known quantum algorithms, including Shor's factoring algorithm. There is therefore a large difference in computational power between normalizer circuits over explicitly decomposed versus black box groups. In fact, we show that a version of the problem of decomposing Abelian groups is complete for the complexity class associated with normalizer circuits over black box groups: any such normalizer circuit can be simulated classically given the ability to decompose Abelian groups.
The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.
The integer factorization problem (IFP) underpins the security of RSA, yet becomes efficiently solvable on a quantum computer through Shor's algorithm. Regev's recent high-dimensional variant reduces the circuit size through lattice-based post-processing, but introduces substantial space overhead and lacks practical implementations. Here, we propose a qubit reuse method by intermediate-uncomputation that significantly reduces the space complexity of Regev's algorithm, inspired by reversible computing. Our basic strategy lowers the cost from O(n3/2) O(n^{3/2}) O(n3/2) to O(n5/4) O(n^{5/4}) O(n5/4), and refined strategies achieve O(nlog⁡n) O(n \log n) O(nlogn)which is a space lower bound within this model. Simulations demonstrate the resulting time-space trade-offs and resource scaling. Moreover, we construct and compile quantum circuits that factor N=35 N = 35 N=35, verifying the effectiveness of our method through noisy simulations. A more simplified experimental circuit for Regev's algorithm is executed on a superconducting quantum computer, with lattice-based post-processing successfully retrieving the factors. These results advance the practical feasibility of Regev-style quantum factoring and provide guidance for future theoretical and experimental developments.