Quantum Algorithms

Researchers Cut Quantum Gate Counts for Group Decomposition

Avatar of Ivy Delaney
October 2, 2026 by Ivy Delaney

A reduction in quantum processing requirements has achieved when decomposing certain mathematical structures known as finite Abelian black-box groups. A new quantum algorithm lowers the total quantum time needed from O~(n 3 T op ) to O~(n (5/2) T op ), where T op represents the cost of performing operations within the group. This decomposition is fundamental to solving problems within the broader area of quantum computation, breaking down complicated calculations into more manageable steps.

By adapting an existing factoring technique, researchers at Wuhan University and Nagoya University have reduced both processing demands and memory requirements compared to previous approaches. They have sharply improved quantum algorithms designed to decompose these complex mathematical structures. These groups are fundamental building blocks in solving problems related to quantum computation; they function like Lego bricks, smaller, independent parts combined to create something larger.

Adapting a factoring technique achieved a reduction in both processing demands and memory requirements when contrasted with earlier methods. The team streamlined how these groups are broken down into their simplest components, mirroring prime factorisation where a number reduces to its constituent primes. The new algorithm reduces the total quantum time needed for this decomposition from O~(n 3 T op ) to O~(n (5/2) T op ).

Abelian group decomposition achieves sharp speedup via optimised lattice structuring

A novel algorithm reduces total quantum time from O~(n3 Top) to O~(n^(5/2) Top), representing a substantial leap in efficiency for decomposing finite Abelian black-box groups. Previously, computations exceeding this complexity were impractical due to excessive resource demands. This improvement unlocks the potential to tackle larger instances of these mathematical structures which are fundamental components within broader quantum computation problems.

Scientists and Nagoya University have lowered both processing requirements and memory usage compared with existing methods developed by Cheung and Mosca. Integer relation lattices can be structured efficiently, preserving circuit advantages while effectively incorporating sampled data. A demonstrated algorithm utilises O(sqrt(n)) quantum circuits; each contains O~(n Top) gates executed no more than O(n) times, a sharp reduction from previous approaches. Effective structuring of integer relation lattices allows incorporation of all sampled generators whilst maintaining a lattice-reduction dimension limited to O(sqrt(n)).

The team lowered total quantum time requirements to O~(n^(5/2) Top), alongside reducing required quantum space down to just O(n) qubits, representing substantial gains over algorithms by Cheung and Mosca which previously demanded O~(n3 Top). Gate counts also decreased from O~(n2 Top) to O~(n^(3/2) Top).

Algorithm limitations necessitate efficient encoding and reversibility for practical quantum computation

Decomposition of finite Abelian black-box groups is essential to progress in areas like cryptography and materials science; it allows complex calculations to be broken down into more manageable steps suitable for quantum computers. However, the algorithm’s performance depends on unique encodings for each group element alongside reversible operations costing at least the square root of the group’s size. The team refined techniques originating in Regev’s factoring algorithm to decompose these mathematical groupings more efficiently, they are essential building blocks within quantum computation allowing complex problems to be broken down into smaller parts. Their new method streamlines analysis by utilising ‘lattice reduction’, a process simplifying relationships between numbers to find optimal solutions with minimal computational effort. Although this efficiency hinges upon having unique identifiers and swiftly reversible operations for each element within a group, it doesn’t invalidate its contribution to quantum computing research.

The researchers developed a quantum algorithm that decomposes finite Abelian black-box groups of order up to 2^n more effectively than previous methods. This decomposition is important because it simplifies complex calculations needed in fields such as cryptography and materials science, making them suitable for processing on quantum computers. The algorithm achieves reductions in both the total quantum time required, down to O~(n^(5/2) Top), and the necessary qubits, decreasing from O(n2) to O(n). Authors suggest further work will focus on maintaining circuit advantages through efficient structuring of integer relation lattices used within the process.

👉 More information
🗞 Improved Quantum Algorithms for Black-Box Abelian Group Decomposition
✍️ Junrong Luo and Yinan Li (Wuhan University); Francois Le Gall (Nagoya University)
🧠 ArXiv: https://arxiv.org/abs/2609.36480

More like this
Quantum AlgorithmsResearchers Bound Errors in Quantum Simulations Using New Sampling Method
Quantum AlgorithmsResearchers Bound Quantum Advantage with Permutation Symmetry
Quantum AlgorithmsBruxelles Team Derives Optimal Quantum Algorithm Building Blocks
Quantum AlgorithmsParityQC & Innsbruck team’s EO maps algorithms to spin qubit hardware
Stay current

See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.

Tags:
quantum algorithms
Avatar of Ivy Delaney

Ivy Delaney

Ivy Delaney has been working with neural networks and machine learning since the mid-nineties, back when a couple of hidden layers and a long afternoon of training counted as ambitious. She has watched the field go from academic curiosity to the thing quietly running underneath everything, and she brings that long view to quantum computing. For Quantum Zeitgeist she covers the ground where the two fields meet. That means quantum machine learning and the variational algorithms it leans on, and it also means the less glamorous but more interesting story of classical machine learning already doing real work inside quantum machines, decoding error-correcting codes, calibrating noisy hardware and learning the error models that simulators depend on. She writes about the hardware those algorithms have to run on too, and about the post-quantum cryptography scramble that the same hardware has set off. Her stories typically start with the paper, whether that is peer-reviewed work, conference proceedings or an arXiv preprint, with the source linked so you can hold a claim up against the research it came from. She is unimpressed by benchmarks that will not say what they beat, and by demonstrations that only work in the press release.

Latest Posts by Ivy Delaney: