⚛️ lattice

Exponential-in- $N_c^2$ cost reduction of product-formula-based quantum simulations of quantum chromodynamics

This paper demonstrates that by optimizing the exponentiated-Hamiltonian decomposition for product-formula algorithms, the T-gate cost of simulating quantum chromodynamics in the electric basis can be reduced by a factor of nearly $10^{14}$ , effectively removing an exponential-in- $N_c^2$ overhead previously attributed to the method.

Original authors: Zohreh Davoudi, Jesse R. Stryker

Published 2026-08-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Zohreh Davoudi, Jesse R. Stryker

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The universe is held together by forces that are invisible to the naked eye but govern the very existence of matter. Among these, the strong nuclear force is the most powerful, binding quarks and gluons into protons and neutrons, which in turn form the atomic nuclei of every star and planet. To understand how this force behaves, especially in the chaotic, high-energy environments of particle colliders or the early universe, scientists rely on a mathematical framework called quantum chromodynamics. While classical supercomputers can calculate the properties of matter at rest, they struggle immensely when trying to simulate how these particles move and interact in real time. The equations become so complex that the computers run out of memory and processing power long before they can reach a meaningful answer.

This is where quantum computers enter the story. Unlike classical machines that process information in bits of zero or one, quantum computers use quantum bits, or qubits, which can exist in multiple states at once. This unique ability makes them theoretically perfect for simulating the quantum world. However, turning this potential into reality requires translating the laws of physics into a language the quantum computer can understand: a sequence of logical operations known as gates. For years, the most common method for doing this translation has been to break the complex motion of particles into tiny, manageable steps. While this approach works in theory, the number of steps required to simulate even a small patch of space has been so astronomically large that it seemed impossible to run on any machine we could build in the foreseeable future. The cost was not just high; it was prohibitive, effectively locking the door on realistic simulations of the strong force.

A team of researchers, led by Zohreh Davoudi and Jesse R. Stryker, has found a way to unlock that door by drastically reducing the number of steps needed. Their work focuses on a specific technique used to simulate the strong force, known as the product-formula method. Imagine trying to walk across a vast, rugged landscape. The traditional method, used in previous studies, was like taking a step for every single blade of grass you encountered, requiring you to lift your foot and place it down millions of times just to cross a small field. The researchers realized that this approach was taking far more steps than necessary because it was treating every tiny movement as a separate, unique event. By rethinking how these movements are grouped and calculated, they discovered a way to take much longer, more efficient strides without losing accuracy.

The team applied their new strategy to the mathematical descriptions of the strong force, specifically looking at how particles interact on a grid, or lattice, which is a standard way physicists model these forces. They focused on two types of interactions: the movement of particles from one point to another, and the magnetic-like forces that act on the loops of the grid. In previous calculations, simulating these loops required a staggering number of individual operations, estimated to be in the quadrillions for a single step of the simulation. The researchers showed that by using a more intelligent way to break down the math, they could eliminate a massive amount of redundant work. Instead of performing quadrillions of operations, their method requires only about a million. This is a reduction by a factor of nearly one hundred trillion.

This improvement is not a minor tweak; it is a fundamental shift in the feasibility of the task. The researchers demonstrated that their method works for the simplest versions of the theory and scales effectively to the complex version that describes our actual universe. They compared their results against the best previous estimates and found that the new approach removes a factor of complexity that grows exponentially with the number of particle types involved. While the previous methods suggested that simulating the strong force would require a quantum computer with capabilities far beyond what is currently imaginable, the new calculation brings the resource requirements down to a level that, while still challenging, is within the realm of possibility for future machines.

The significance of this finding lies in what it enables. By cutting the computational cost by such a massive margin, the researchers have moved the simulation of real-time quantum chromodynamics from the category of "theoretically possible but practically impossible" to "a serious engineering challenge." This does not mean the simulation will happen tomorrow, but it means that the path forward is no longer blocked by an insurmountable wall of numbers. The work highlights that the path to useful quantum simulation is not just about building better hardware, but also about refining the algorithms that tell the hardware what to do. As the field of quantum computing matures, such continuous improvements in the software side are just as critical as the hardware itself.

The researchers also placed their findings in the context of other emerging strategies. There are other methods being developed that aim to simulate these forces with even greater efficiency, some of which promise to reduce the cost even further. However, those methods often rely on different assumptions or require different types of quantum computers. The approach taken by this team is notable because it works within the most widely used framework for these simulations, making it immediately applicable to the vast amount of existing research and development. They showed that even within the established methods, there is still room for dramatic discovery. The key was recognizing that the way the mathematical terms were being split apart was creating unnecessary work, and that a more direct path existed.

Ultimately, this paper serves as a reminder that the journey to harness quantum computers for fundamental physics is a marathon of both hardware and software innovation. The strong force remains one of the most difficult puzzles in physics, and solving it requires tools that can handle extreme complexity. By demonstrating that the cost of simulation can be reduced by orders of magnitude through better mathematical organization, the researchers have provided a crucial piece of the puzzle. Their work suggests that the dream of simulating the birth of the universe or the collision of particles in real time is not a distant fantasy, but a goal that is becoming increasingly attainable as our understanding of the algorithms deepens. The barrier was never just the size of the machine, but the efficiency of the map we used to navigate it.

Technical Summary: Exponential-in- $N_c$ Cost Reduction of Product-Formula-Based Quantum Simulations of QCD

Problem Statement
Quantum algorithms for simulating Quantum Chromodynamics (QCD) on a lattice have matured since early work by Byrnes and Yamamoto, yet the resource costs remain prohibitively high for realistic quantum computers. The most common approach, product-formula (PF) decompositions (Trotterization), faces a significant bottleneck in the Kogut-Susskind lattice formulation when using the irreducible-representation (irrep or electric) basis.

Previous state-of-the-art methods, specifically the seminal work by Kan and Nam, improved the scaling of gate complexity from $O(\Lambda^8(N_c^2-1))$ to $O(\Lambda \text{polylog}(\Lambda))$ per Trotter step by avoiding direct Pauli decompositions. However, this method relies on an "even-odd" splitting of every bosonic ladder operator within the Hamiltonian terms. For non-Abelian gauge theories like $SU(N_c)$ , this results in an explosion of subevolutions (terms to be simulated) per Trotter step. For $SU(3)$ (QCD), this approach requires approximately $10^{15}$ subevolutions per magnetic (plaquette) term, creating a "staggering multiplicative cost" that acts as a roadblock for near-term and potentially far-term hardware implementations.

Methodology
The authors propose a refined strategy for subdividing Hamiltonian operators that significantly reduces the number of required subevolutions. The core methodology builds upon techniques developed in their previous works (PRD 112, 014508 (2025); Quantum 7, 1213 (2023)), utilizing Singular Value Decomposition (SVD) and graph-theoretic interpretations of operator mixing.

Operator Splitting Strategy: Unlike the previous method which splits all ladder operators in a term, the authors demonstrate that splitting a single ladder operator factor (via an even-odd split) is sufficient to render the resulting summands block-diagonalizable into $2 \times 2$ blocks.
Diagonalization via SVD: Once split, these summands generate rotations in two-dimensional subspaces. The authors utilize an SVD-based procedure (often involving an ancilla qubit) to analytically diagonalize these terms, allowing for efficient circuit implementation.
Graph-Theoretic Interpretation: The authors interpret the Hamiltonian terms as graphs where nodes represent basis states and edges represent non-zero matrix elements. The goal is to color these graphs such that each color class corresponds to a set of non-overlapping edges (sub-Hamiltonians) that can be diagonalized. The previous method corresponds to an excessive coloring (splitting every degree of freedom), whereas the new method finds a minimal coloring that still allows for closed-form diagonalization.
Application to $SU(N_c)$ : The method is applied systematically to $U(1)$ , $SU(2)$ , and $SU(3)$ lattice gauge theories in arbitrary dimensions, focusing on the off-diagonal hopping (fermion-gauge interaction) and plaquette (magnetic) terms.

Key Contributions and Results
The primary contribution is the identification and removal of an exponential factor in the number of subevolutions required per Trotter step.

Reduction in Subevolutions ( $\Gamma$ ): The authors show that the number of summands $\Gamma$ $Γ$ in the product-formula decomposition can be reduced by a factor of $O(2^{4(N_c^2-1)})$ $O (2^{4 (N_{c}^{2} - 1)})$ compared to the Kan and Nam method.
- $U(1)$ : Reduced from 16 to 2 for plaquette terms.
- $SU(2)$ : Reduced from 1,048,576 to 256 for plaquette terms.
- $SU(3)$ (QCD): Reduced from a tightened count of $\approx 2.9 \times 10^{14}$ to 1,062,882 for plaquette terms.
Total Simulation Cost: Since the total gate cost for a second-order product formula scales as $\Gamma^{3/2}$ $Γ^{3/2}$ (due to the dependence of the Trotter step count $s$ $s$ on $\Gamma^{1/2}$ $Γ^{1/2}$ ), the reduction in $\Gamma$ $Γ$ translates to a massive reduction in total T-gate cost.
- For $SU(3)$ QCD simulations, the total cost estimate is reduced by a factor of nearly $10^{14}$ .
- This reduction is independent of simulation parameters such as system size, simulation time, or the electric-field cutoff $\Lambda$ .
Comparison with Other Algorithms:
- Near-Optimal Algorithms (Rhodes et al.): The authors contrast their improved PF results with post-Trotter, near-optimal algorithms (e.g., block-encoding/qubitization). While the near-optimal algorithms offer further improvements (estimated $10^3$ to $10^6$ better than the authors' PF results), the authors' work bridges the gap between the previous inefficient PF estimates and these advanced methods.
- Local-Multiplet Basis (Ciavarella et al.): The authors note that while local-multiplet basis approaches reduce qubit counts, they introduce controlled-plaquette operators whose matrix elements scale polynomially with the cutoff $\Lambda$ (e.g., $\Lambda^{24}$ for 2D), whereas the authors' method maintains a modest $O(\Lambda \text{polylog}(\Lambda))$ scaling.

Significance and Claims
The paper claims that continuous algorithmic improvements are vital for realistic resource estimation in the fault-tolerant era of quantum computing. The authors emphasize that:

Feasibility: The removal of the $O(2^{4(N_c^2-1)})$ factor addresses a specific, previously overlooked inefficiency in the decomposition of non-Abelian gauge theories. This brings the cost of QCD simulations within a more realistic range, though still demanding.
Algorithmic Maturity: The work highlights that the "high cost" estimates of previous years were partly due to suboptimal splitting strategies rather than fundamental physical limits.
Contextual Necessity: While the authors' method significantly improves product-formula efficiency, they acknowledge that near-optimal, post-Trotter algorithms (like those by Rhodes et al.) currently offer superior asymptotic scaling. However, the authors' contribution is essential for understanding the baseline costs of PF methods and demonstrating that even within the PF framework, exponential improvements are possible.
Future Outlook: The paper concludes that the path to feasible QCD simulation requires a holistic analysis involving truncation errors, continuum limits, and state preparation, but that the algorithmic cost reductions presented here are a critical step toward making such simulations possible on future quantum supercomputers.

The authors explicitly state that their work does not propose new experimental hardware or specific physical applications beyond the simulation of QCD dynamics, but rather focuses on the theoretical optimization of the quantum algorithms required to perform such simulations.

Technical Summary: Exponential-in-NcN_cNc​ Cost Reduction of Product-Formula-Based Quantum Simulations of QCD

More like this

Technical Summary: Exponential-in- $N_c$ Cost Reduction of Product-Formula-Based Quantum Simulations of QCD