Universidad Complutense algorithm cuts quantum gate count for particle physics

Researchers at Universidad Complutense de Madrid have developed an algorithm requiring only O(j log₂²j + jn_(qb)) CNOT and single-qubit gates to efficiently manage quantum registers, a potentially significant reduction in the “gate count” that has long constrained complex particle physics simulations. The work proposes a recursive method for (anti)symmetrizing quantum registers by focusing on the last particle added to memory, scaling efficiently for systems ranging from atomic to particle physics.

This approach improves upon previous constructions by almost two powers of j, offering a solution ideally suited for managing variable particle numbers in quantum computing. The team demonstrates its applicability to problems in hadron physics expected to be addressable with future quantum computers.

Iterative Symmetrization Algorithm for Quantum Registers

This reduction addresses a major bottleneck in quantum computing, where minimizing gate complexity is important for scaling up simulations of many-body systems. The algorithm also manages auxiliary qubit overhead with relative economy, requiring 3j + ⌈ log₂j⌉ + O( max(nqb, log₂j)) clean auxiliary qubits. The researchers applied this algorithm to problems in hadron physics, anticipating that a full-scale quantum computer will benefit from its capabilities.

The core of the algorithm lies in how it handles the addition or removal of particles from quantum memory. In a quantum-register representation, one divides the quantum memory into n registers of size nqb each.

The (anti)symmetrizing operator constructed for this purpose depends on the quantum numbers of the additional particle being introduced or “created”. “Because main parts of this algorithm seem to have been rediscovered by further researchers, and because in deploying it we have seen certain improvements which can be effected, we here wish to reappraise it,” the authors state, indicating a refinement of existing techniques.

Generalized Dicke State Construction with CNOT Gates

This efficiency stems from a recursive approach that (anti)symmetrizes each newly added or destroyed particle relative to the existing, already (anti)symmetrized register. Preparation of an additional register necessitates a specific number of qubits determined by the overall system size, with a cost of single-qubit and CNOT gates alongside auxiliary qubits.

Algorithm’s Efficiency Gain Over Prior Methods

The algorithm’s efficiency stems from a refined implementation of a subroutine which disentangles auxiliary registers used to track particle multiplicities. This optimization addresses a key bottleneck in earlier versions of the algorithm, reducing computational costs for simulations involving large numbers of particles.

By replacing networks reliant on locating the largest value with the Shukla-Vedula algorithm for preparing uniform superpositions, the team achieved an improvement upon a previously published construction, detailed in Appendix An of the original work, by nearly two powers of j, a parameter representing the system size. The resulting algorithm now performs comparably to the most efficient methods currently available, while also proving particularly well-suited for managing quantum memory dynamically as the number of particles changes during a simulation. A cornerstone of Quantum Mechanics is the symmetrization / antisymmetrization of wavefunctions upon exchanging integer / half-integer quanta.

Step Symmetrizer Operator for Mode Introduction

The construction of the (anti)symmetrizing operator hinges on the quantum numbers of the particle being added to a quantum register, allowing for precise control over the resulting quantum state. This dependence is critical for accurately modeling complex physical systems, particularly those involving identical particles where indistinguishability is a fundamental property. The algorithm’s efficiency stems from its ability to extend existing symmetry, or anti-symmetry, to a newly introduced particle, rather than rebuilding it from scratch.

Quantum Symmetrization in Hadron Physics Applications

This improvement is particularly important given that (anti)symmetrization is a fundamental step not only in particle creation and annihilation, but also in state preparation and time evolution within quantum simulations. J. J. Gálvez-Viruet.

A sorting-based construction, for example, achieves O(n log²n logM) gate complexity, using asymptotically optimal sorting networks, but still demands significant resources for larger systems. The team notes that while elements of the algorithm have been independently rediscovered, they have identified further improvements in its deployment. The work offers a pathway toward gaining new insights into areas where lattice gauge theory currently struggles to provide first-principle results, such as jet fragmentation and neutron star equations of state.

Encoding Quantum States with Variable Particle Number

This dependency is a key feature enabling the efficient management of variable particle numbers, a capability important for modeling systems where particle creation and annihilation occur. The algorithm’s design bypasses the need to pre-define the total particle count, a limitation of many existing methods. This approach achieves efficiency through a recursive process, (anti)symmetrizing the last particle added to memory relative to all previously (anti)symmetrized particles.

First-Quantized Algorithms & Sorting Network Complexity

Existing algorithms for creating symmetric quantum states require either strictly ordered configurations or post-selection steps to manage auxiliary labels, impacting computational efficiency. The Universidad Complutense de Madrid team proposes a recursive algorithm (anti)symmetrizing the last particle added to memory, each time one is created or destroyed, respect to the rest of already (anti)symmetrized ones.

Given a generalized Dicke state (GDS) of (j-1) quantum registers, each assigned to a particle, the algorithm produces another GDS of j registers (of nqb qubits each) using a mere O(j log22j + jn_(qb)) CNOT and single-qubit gates, and 3j + ⌈ log2j⌉ + O( max(nqb, log_2j)) clean auxiliary qubits.

Boson Implementation: Handling Repeated Occupations

The team’s algorithm distinguishes itself by focusing on disentangling auxiliary records associated with these repeated occupations, a step that impacts overall scaling. This allows for sequential preparation that scales quadratically in particle number, up to logarithmic factors, with a linear contribution from the register width. The improvement over previous methods stems from a modification of the team’s earlier step-symmetrization algorithm, specifically addressing inefficiencies related to the “Locate the Largest” (LL) algorithm and a subroutine termed UDD.

By incorporating the main particle register with auxiliary qubit registers, labeled B and C, each consisting of j qubits, the algorithm refines the process of handling repeated occupations. The researchers introduce two auxiliary qubit registers, B and C, each containing j qubits, where j represents the number of occupied registers, to track these repeated modes. This approach avoids unnecessary increases in asymptotic costs for large particle numbers.

A key distinction between bosonic symmetrization and fermionic antisymmetrization lies in this UDD step; the fermionic specialization bypasses the need to disentangle auxiliary records. The algorithm’s efficiency is particularly notable when inserting a single mode into an already symmetrized state, a common operation in many-body physics simulations.

👉 More information
🗞 Efficient Iterative Symmetrization algorithm for quantum computing and hadron applications
✍️ Nahia J. Dios-Bilbao, J. J. Gálvez-Viruet, Felipe J. Llanes-Estrada and Mario Logrosán-Álvarez (Física Teórica & IPARCOS, Universidad Complutense de Madrid, Fac. de CC. Físicas, Plaza de las Ciencias 1, Madrid, Spain); Adrián Castaño-García
🧠 ArXiv: https://arxiv.org/abs/2611.18091v1

Stay current

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

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: