Skip to content
Preprint

Improved Quantum Algorithms for Black-Box Abelian Group Decomposition

Sep 2026 · 0 citations
Physics

TL;DR

This work gives 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, and proves that the integer relation lattices used in the algorithm admit, with high probability, integral bases whose vectors have Euclidean norm at most exp(O(sqrt(n).

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

View source

Similar papers

Sep 2026

Quantum Algorithms for Minimum Generating Set

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

Bireswar Das, U. Kumar, Kavita Samant et al. · 0 citations
Preprint Nov 2026

Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis

The hidden subgroup problem (HSP) unifies many of the best-known quantum speed-ups. For abelian groups it is solved efficiently by weak Fourier sampling, but for non-abelian groups, which include the cases relevant to graph isomorphism and lattice-based cryptography, the right measurement basis is crucial and often unk...

Oliver O'Brien · 0 citations
Preprint Oct 2026

An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group

Consider a quantum state vector proportional to any given column of the character table of the symmetric group ($S_n$), corresponding to a superposition over the irreps weighted by the character values. It was recently argued that sampling from this state is classically hard under reasonable complexity-theoretic assump...

Dikshant Rathore, Leo Zhou · 1 citation
Preprint Sep 2026

Classical and Quantum Simulation of All-to-All Quantum Dynamics in Logarithmic Space

We study both the classical and the quantum complexity of the problem of estimating disorder-averaged quench dynamics for all-to-all spin Hamiltonians such as quantum Hopfield, Sherrington--Kirkpatrick (SK) or Dicke-type models. Disorder averaging restores permutation invariance in this setting, so states of $N$ spins...

M. Lutz, R. Trivedi, J. Cirac · 0 citations
Preprint Nov 2026

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantu...

Chandrima Kayal, Rajat Mittal, Manaswi Paraashar et al. · 0 citations
Preprint Oct 2026

Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations

The framework lifts multivariable polynomial synthesis to quantum channel transformations, and synthesizes any finite jointly contractive family of noncommutative polynomial maps as completely positive operations, allowing coherent interference among Kraus histories.

Zhe-Yu Shen, Yu-Sen Wu, Xiao Yuan et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.