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:2608.21258

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

Zohreh Davoudi, Jesse R. Stryker

hep-lathep-phnucl-thquant-phSubmitted Aug 21, 2026• Announced Aug 24, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum algorithms for simulating quantum chromodynamics (QCD) have matured steadily since the pioneering work of Byrnes and Yamamoto [PRA 73, 022328 (2006)]. The most popular strategies for Hamiltonian simulation involve product-formula decompositions. However, the application of product-formula methods to SU($N_c$) lattice gauge theories by Byrnes and Yamamoto leads to $O(Λ^{8(N_c^2-1)})$ gate complexity per Trotter step, where $Λ$ is the bosonic cutoff in the electric (i.e., irreducible-representation) basis. A seminal work by Kan and Nam [arXiv:2107.12769 (2021)] significantly improves over such an undesirable cost and reports an $O\big(Λ\text{polylog}(Λ)\big)$ scaling, yet it still calls for an unrealistically large number of quantum gates. Here, we illuminate one of the reasons behind this high cost estimate and show that a factor of size $O(2^{4(N_c^2-1)})$ can be removed from the per-Trotter-step cost estimate by Kan and Nam. We specifically show that, by using methods developed in our past works [PRD 112, 014508 (2025); Quantum 7, 1213 (2023)], exponentiated-Hamiltonian decomposition---a necessary step in the application of product-formula algorithms---can be performed far more efficiently than previously thought. Our method reduces the T-gate cost estimate of QCD simulations using a second-order product formula by a factor of nearly $10^{14}$, independent of simulation parameters and sizes. Focusing on simulations in the electric basis, we further contrast our results with other methods: the local-multiplet basis approach of Ciavarella, Klco, and Savage [PRD 103, 094501 (2021)] and the near-optimal algorithm of Rhodes, Kreshchuk, and Pathak [PRX Quantum 5, 040347 (2024)]. This work highlights the importance of continued algorithmic improvement to bringing the quantum-simulation cost of QCD within reach of realistic quantum computers.

Comments
16 pages + bibliography, 3 figures

Related papers

Practical Estimation of Trotter Error for Hamiltonian Simulation

William Maxwell, Pablo A. M. Casares, Robert A. Lang +7 more

Trotter product formulas are a leading approach for Hamiltonian simulation on quantum computers, yet their practical performance has remained difficult to assess due to the challenge of accurately estimating the Trotter error. In this work, we develop new theoretical results, algorithms, and software tools that advance the state-of-the-art in Trotter error estimation by orders of magnitude in both scale and accuracy. On the theoretical side, we prove that in the asymptotic limit the error of a product formula depends on the diagonal elements of the Baker-Campbell-Hausdorff (BCH) error operator in the eigenbasis of the Hamiltonian, rather than its full spectral norm -- yielding an improved scaling for Hamiltonian simulation using product formulas. On the algorithmic side, we introduce a compact representation of the BCH expansion that reduces the number of commutators from $\mathcal{O}(n^3)$ to $\mathcal{O}(n)$ for second-order, and from $\mathcal{O}(n^5)$ to $\mathcal{O}(n^2)$ for fourth-order formulas on $n$ fragments, complemented by an importance sampling scheme to further reduce the computational cost. We provide implementations of these techniques in software and demonstrate their power on two applications: (i) X-ray absorption spectroscopy of an electronic Hamiltonian (Li$_4$Mn$_2$O) at up to 56 qubits using tensor networks; and (ii) vibronic dynamics of naphthalene at over 100 qubits using ML-MCTDH, where we find that naive analytical bounds overestimate the required number of Trotter steps by nearly five orders of magnitude. Our framework enables, for the first time, the accurate estimation of Trotter error at practically relevant system sizes, providing a foundation for fair algorithmic comparisons and rational design of product formulas.

quant-pharXiv:2606.30738•Jul 1, 2026•0 citations

Well-conditioned multiproduct Hamiltonian simulation

Guang Hao Low, Vadym Kliuchnikov, Nathan Wiebe

Product formula approximations of the time-evolution operator on quantum computers are of great interest due to their simplicity, and good scaling with system size by exploiting commutativity between Hamiltonian terms. However, product formulas exhibit poor scaling with the time $t$ and error $ε$ of simulation as the gate cost of a single step scales exponentially with the order $m$ of accuracy. We introduce well-conditioned multiproduct formulas, which are a linear combination of product formulas, where a single step has polynomial cost $\mathcal{O}(m^2\log{(m)})$ and succeeds with probability $Ω(1/\operatorname{log}^2{(m)})$. Our multiproduct formulas imply a simple and generic simulation algorithm that simultaneously exploits commutativity in arbitrary systems and has a worst-case cost $\mathcal{O}(t\log^{2}{(t/ε)})$ which is optimal up to poly-logarithmic factors. In contrast, prior Trotter and post-Trotter Hamiltonian simulation algorithms realize only one of these two desirable features. A key technical result of independent interest is our solution to a conditioning problem in previous multiproduct formulas that amplified numerical errors by $e^{Ω(m)}$ in the classical setting, and led to a vanishing success probability $e^{-Ω(m)}$ in the quantum setting.

arXiv:1907.11679•Jul 26, 2019•18 citations

Exponential Improvements in the Simulation of Lattice Gauge Theories Using Near-Optimal Techniques

Mason L. Rhodes, Michael Kreshchuk, Shivesh Pathak

We report a first-of-its-kind analysis on post-Trotter simulation of U(1), SU(2), and SU(3) lattice gauge theories including fermions in arbitrary spatial dimension. We provide explicit circuit constructions as well as T -gate counts and logical qubit counts for Hamiltonian simulation. We find a reduction of up to 25 orders of magnitude in space-time volume over Trotter methods for simulations of non-Abelian lattice gauge theories relevant to the standard model. This improvement results from our algorithm having polynomial scaling with the number of colors in the gauge theory, achieved by utilizing oracle constructions relying on the sparsity of physical operators, in contrast to the exponential scaling seen in state-of-the-art Trotter methods, which employ explicit mappings onto Pauli operators. Our work demonstrates that the use of advanced algorithmic techniques leads to dramatic reductions in the cost of simulating fundamental interactions, bringing it in step with resources required for first-principles quantum simulation of chemistry. Published by the American Physical Society 2024

arXiv:2405.10416•PRX Quantum•Dec 23, 2024•25 citations

Universal framework with exponential speedup for the quantum simulation of quantum field theories including QCD

Jad C. Halimeh, Masanori Hanada, Shunji Matsuura

We present a quantum simulation framework universally applicable to a wide class of quantum systems, including quantum field theories such as quantum chromodynamics (QCD). Specifically, we generalize an efficient quantum simulation protocol developed for bosonic theories in [Halimeh et al., arXiv:2411.13161] which, when applied to Yang-Mills theory, demonstrated an exponential resource advantage with respect to the truncation level of the bosonic modes, to systems with both bosons and fermions using the Jordan-Wigner transform and also the Verstraete-Cirac transform. We apply this framework to QCD using the orbifold lattice formulation and achieve an exponential speedup compared to previous proposals. As a by-product, exponential speedup is achieved in the quantum simulation of the Kogut-Susskind Hamiltonian, the latter being a special limit of the orbifold lattice Hamiltonian. In the case of Hamiltonian time evolution of a theory on an $L^d$ spatial lattice via Trotterization, one Trotter step can be realized using $\mathcal{O}(L^d)$ numbers of CNOT gates, Hadamard gates, phase gates, and one-qubit rotations. We show this analytically for any matter content and $\mathrm{SU}(N)$ gauge group with any $N$. Even when we use the Jordan-Wigner transform, we can utilize the cancellation of quantum gates to significantly simplify the quantum circuit. We also discuss a block encoding of the Hamiltonian as a linear combination of unitaries using the Verstraete-Cirac transform. Our protocols do not assume oracles, but rather present explicit constructions with rigorous resource estimations without a hidden cost, and are thus readily implementable on a quantum computer.

arXiv:2506.18966•Jun 23, 2025•0 citations

Randomized product formulas beyond optimal deterministic scaling

Leeseok Kim, Luis Pedro García-Pintos

Product formulas, also known as Trotter formulas, are among the most widely used and practical methods for simulating quantum systems on quantum computers. Here we introduce two new classes of randomized product formulas for simulating Hamiltonians with separated energy scales, $H=A+αB$, where $α$ is small. In the standard access model, where one can implement exponentials of $A$ and $B$ separately, our randomized formulas achieve $\mathcal O(α^2)$ error scaling at the cost of only doubling the gate depth of the corresponding deterministic formula. We further prove an $Ω(α)$ lower bound for deterministic product formulas. In a stronger access model, allowing exponentials of $A+αB_\ell$ for $B = \sum_{\ell}B_\ell$, our randomized formula, based on Trotter Heuristic Resource Improved Formulas for Time-dynamics (THRIFT)~[J. L. Bosse et al., Nat. Commun. 16, 2673 (2025)], achieves $\mathcal O(α^3)$ error scaling with only constant-factor expected gate overhead. We also establish an $Ω(α^2)$ lower bound for deterministic product formulas in this access model. Numerical simulations confirm gate-count reductions for simulating physically motivated systems.

quant-pharXiv:2608.07720•Aug 11, 2026•0 citations

Average-Case Speedup for Product Formulas

Chi-Fang Chen, Fernando G. S. L. Brandão

Abstract Quantum simulation is a promising application of future quantum computers. Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. For an accurate product formula approximation, the state-of-the-art gate complexity depends on the number of terms in the Hamiltonian and a local energy estimate. In this work, we give evidence that product formulas, in practice, may work much better than expected. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states, while the existing estimate is for the worst states. For general k-local Hamiltonians and higher-order product formulas, we obtain gate count estimates for input states drawn from any orthogonal basis. The gate complexity significantly improves over the worst case for systems with large connectivity. Our typical-case results generalize to Hamiltonians with Fermionic terms, with input states drawn from a fixed-particle number subspace, and with Gaussian coefficients (e.g., the SYK models). Technically, we employ a family of simple but versatile inequalities from non-commutative martingales called uniform smoothness, which leads to Hypercontractivity, namely p-norm estimates for k-local operators. This delivers concentration bounds via Markov’s inequality. For optimality, we give analytic and numerical examples that simultaneously match our typical-case estimates and the existing worst-case estimates. Therefore, our improvement is due to asking a qualitatively different question, and our results open doors to the study of quantum algorithms in the average case.

arXiv:2111.05324•Communications in Mathematical Physics•Feb 1, 2024•17 citations
Exponential-in-Nc2N_c^2Nc2​ cost reduction of product-formula-based quantum simulations of quantum chromodynamics
Quantum algorithms for simulating quantum chromodynamics (QCD) have matured steadily since the pioneering work of Byrnes and Yamamoto [PRA 73, 022328 (2006)]. The most popular strategies for Hamiltonian simulation involve product-formula decompositions. However, the application of product-formula methods to SU(NcN_cNc​) lattice gauge theories by Byrnes and Yamamoto leads to O(Λ8(Nc2−1))O(Λ^{8(N_c^2-1)})O(Λ8(Nc2​−1)) gate complexity per Trotter step, where ΛΛΛ is the bosonic cutoff in the electric (i.e., irreducible-representation) basis. A seminal work by Kan and Nam [arXiv:2107.12769 (2021)] significantly improves over such an undesirable cost and reports an O(Λpolylog(Λ))O\big(Λ\text{polylog}(Λ)\big)O(Λpolylog(Λ)) scaling, yet it still calls for an unrealistically large number of quantum gates. Here, we illuminate one of the reasons behind this high cost estimate and show that a factor of size O(24(Nc2−1))O(2^{4(N_c^2-1)})O(24(Nc2​−1)) can be removed from the per-Trotter-step cost estimate by Kan and Nam. We specifically show that, by using methods developed in our past works [PRD 112, 014508 (2025); Quantum 7, 1213 (2023)], exponentiated-Hamiltonian decomposition---a necessary step in the application of product-formula algorithms---can be performed far more efficiently than previously thought. Our method reduces the T-gate cost estimate of QCD simulations using a second-order product formula by a factor of nearly 101410^{14}1014, independent of simulation parameters and sizes. Focusing on simulations in the electric basis, we further contrast our results with other methods: the local-multiplet basis approach of Ciavarella, Klco, and Savage [PRD 103, 094501 (2021)] and the near-optimal algorithm of Rhodes, Kreshchuk, and Pathak [PRX Quantum 5, 040347 (2024)]. This work highlights the importance of continued algorithmic improvement to bringing the quantum-simulation cost of QCD within reach of realistic quantum computers.
Trotter product formulas are a leading approach for Hamiltonian simulation on quantum computers, yet their practical performance has remained difficult to assess due to the challenge of accurately estimating the Trotter error. In this work, we develop new theoretical results, algorithms, and software tools that advance the state-of-the-art in Trotter error estimation by orders of magnitude in both scale and accuracy. On the theoretical side, we prove that in the asymptotic limit the error of a product formula depends on the diagonal elements of the Baker-Campbell-Hausdorff (BCH) error operator in the eigenbasis of the Hamiltonian, rather than its full spectral norm -- yielding an improved scaling for Hamiltonian simulation using product formulas. On the algorithmic side, we introduce a compact representation of the BCH expansion that reduces the number of commutators from O(n3)\mathcal{O}(n^3)O(n3) to O(n)\mathcal{O}(n)O(n) for second-order, and from O(n5)\mathcal{O}(n^5)O(n5) to O(n2)\mathcal{O}(n^2)O(n2) for fourth-order formulas on nnn fragments, complemented by an importance sampling scheme to further reduce the computational cost. We provide implementations of these techniques in software and demonstrate their power on two applications: (i) X-ray absorption spectroscopy of an electronic Hamiltonian (Li4_44​Mn2_22​O) at up to 56 qubits using tensor networks; and (ii) vibronic dynamics of naphthalene at over 100 qubits using ML-MCTDH, where we find that naive analytical bounds overestimate the required number of Trotter steps by nearly five orders of magnitude. Our framework enables, for the first time, the accurate estimation of Trotter error at practically relevant system sizes, providing a foundation for fair algorithmic comparisons and rational design of product formulas.
Product formula approximations of the time-evolution operator on quantum computers are of great interest due to their simplicity, and good scaling with system size by exploiting commutativity between Hamiltonian terms. However, product formulas exhibit poor scaling with the time ttt and error εεε of simulation as the gate cost of a single step scales exponentially with the order mmm of accuracy. We introduce well-conditioned multiproduct formulas, which are a linear combination of product formulas, where a single step has polynomial cost O(m2log⁡(m))\mathcal{O}(m^2\log{(m)})O(m2log(m)) and succeeds with probability Ω(1/log⁡2(m))Ω(1/\operatorname{log}^2{(m)})Ω(1/log2(m)). Our multiproduct formulas imply a simple and generic simulation algorithm that simultaneously exploits commutativity in arbitrary systems and has a worst-case cost O(tlog⁡2(t/ε))\mathcal{O}(t\log^{2}{(t/ε)})O(tlog2(t/ε)) which is optimal up to poly-logarithmic factors. In contrast, prior Trotter and post-Trotter Hamiltonian simulation algorithms realize only one of these two desirable features. A key technical result of independent interest is our solution to a conditioning problem in previous multiproduct formulas that amplified numerical errors by eΩ(m)e^{Ω(m)}eΩ(m) in the classical setting, and led to a vanishing success probability e−Ω(m)e^{-Ω(m)}e−Ω(m) in the quantum setting.
We report a first-of-its-kind analysis on post-Trotter simulation of U(1), SU(2), and SU(3) lattice gauge theories including fermions in arbitrary spatial dimension. We provide explicit circuit constructions as well as T -gate counts and logical qubit counts for Hamiltonian simulation. We find a reduction of up to 25 orders of magnitude in space-time volume over Trotter methods for simulations of non-Abelian lattice gauge theories relevant to the standard model. This improvement results from our algorithm having polynomial scaling with the number of colors in the gauge theory, achieved by utilizing oracle constructions relying on the sparsity of physical operators, in contrast to the exponential scaling seen in state-of-the-art Trotter methods, which employ explicit mappings onto Pauli operators. Our work demonstrates that the use of advanced algorithmic techniques leads to dramatic reductions in the cost of simulating fundamental interactions, bringing it in step with resources required for first-principles quantum simulation of chemistry. Published by the American Physical Society 2024
We present a quantum simulation framework universally applicable to a wide class of quantum systems, including quantum field theories such as quantum chromodynamics (QCD). Specifically, we generalize an efficient quantum simulation protocol developed for bosonic theories in [Halimeh et al., arXiv:2411.13161] which, when applied to Yang-Mills theory, demonstrated an exponential resource advantage with respect to the truncation level of the bosonic modes, to systems with both bosons and fermions using the Jordan-Wigner transform and also the Verstraete-Cirac transform. We apply this framework to QCD using the orbifold lattice formulation and achieve an exponential speedup compared to previous proposals. As a by-product, exponential speedup is achieved in the quantum simulation of the Kogut-Susskind Hamiltonian, the latter being a special limit of the orbifold lattice Hamiltonian. In the case of Hamiltonian time evolution of a theory on an LdL^dLd spatial lattice via Trotterization, one Trotter step can be realized using O(Ld)\mathcal{O}(L^d)O(Ld) numbers of CNOT gates, Hadamard gates, phase gates, and one-qubit rotations. We show this analytically for any matter content and SU(N)\mathrm{SU}(N)SU(N) gauge group with any NNN. Even when we use the Jordan-Wigner transform, we can utilize the cancellation of quantum gates to significantly simplify the quantum circuit. We also discuss a block encoding of the Hamiltonian as a linear combination of unitaries using the Verstraete-Cirac transform. Our protocols do not assume oracles, but rather present explicit constructions with rigorous resource estimations without a hidden cost, and are thus readily implementable on a quantum computer.
Product formulas, also known as Trotter formulas, are among the most widely used and practical methods for simulating quantum systems on quantum computers. Here we introduce two new classes of randomized product formulas for simulating Hamiltonians with separated energy scales, H=A+αBH=A+αBH=A+αB, where ααα is small. In the standard access model, where one can implement exponentials of AAA and BBB separately, our randomized formulas achieve O(α2)\mathcal O(α^2)O(α2) error scaling at the cost of only doubling the gate depth of the corresponding deterministic formula. We further prove an Ω(α)Ω(α)Ω(α) lower bound for deterministic product formulas. In a stronger access model, allowing exponentials of A+αBℓA+αB_\ellA+αBℓ​ for B=∑ℓBℓB = \sum_{\ell}B_\ellB=∑ℓ​Bℓ​, our randomized formula, based on Trotter Heuristic Resource Improved Formulas for Time-dynamics (THRIFT)~[J. L. Bosse et al., Nat. Commun. 16, 2673 (2025)], achieves O(α3)\mathcal O(α^3)O(α3) error scaling with only constant-factor expected gate overhead. We also establish an Ω(α2)Ω(α^2)Ω(α2) lower bound for deterministic product formulas in this access model. Numerical simulations confirm gate-count reductions for simulating physically motivated systems.
Abstract Quantum simulation is a promising application of future quantum computers. Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. For an accurate product formula approximation, the state-of-the-art gate complexity depends on the number of terms in the Hamiltonian and a local energy estimate. In this work, we give evidence that product formulas, in practice, may work much better than expected. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states, while the existing estimate is for the worst states. For general k-local Hamiltonians and higher-order product formulas, we obtain gate count estimates for input states drawn from any orthogonal basis. The gate complexity significantly improves over the worst case for systems with large connectivity. Our typical-case results generalize to Hamiltonians with Fermionic terms, with input states drawn from a fixed-particle number subspace, and with Gaussian coefficients (e.g., the SYK models). Technically, we employ a family of simple but versatile inequalities from non-commutative martingales called uniform smoothness, which leads to Hypercontractivity, namely p-norm estimates for k-local operators. This delivers concentration bounds via Markov’s inequality. For optimality, we give analytic and numerical examples that simultaneously match our typical-case estimates and the existing worst-case estimates. Therefore, our improvement is due to asking a qualitatively different question, and our results open doors to the study of quantum algorithms in the average case.