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

Well-conditioned multiproduct Hamiltonian simulation

Guang Hao Low, Vadym Kliuchnikov, Nathan Wiebe

Published Jul 26, 2019• 95 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1907.11679

Related papers

Multi-Product Hamiltonian Simulation with Explicit Commutator Scaling

Junaid Aftab, Dong An, Konstantina Trivisa

The well-conditioned multi-product formula (MPF), proposed by Low-Kliuchnikov-Wiebe (2019), is a high-order, time-independent Hamiltonian simulation algorithm that implements a linear combination of low-order product formulas. Prior work established its well-conditioned algorithmic construction and near-optimal time and precision dependence, but did not simultaneously provide an explicit error bound in terms of nested commutators, which has left its practical advantage uncertain. In this work, we provide a rigorous complexity analysis of the well-conditioned MPF, explicitly establishing both commutator scaling and near-optimal dependence on time and precision through a rigorous Baker-Campbell-Hausdorff (BCH) and variation-of-parameters-based error analysis. Using our improved complexity estimates, we present several physically relevant applications where the second-order-based MPF asymptotically outperforms the second-order product formula in all three aspects of system size, time, and precision. We further demonstrate that, while MPF yields worse scalings than the best post-Trotter methods in most applications, there exist certain parameter regimes in the nonlocal fast-transform Bogoliubov-de Gennes model where MPF can outperform both leading post-Trotter methods and product formulas with fixed or adaptively optimized order.

arXiv:2403.08922•Mar 13, 2024•29 citations

On the commutator scaling in Hamiltonian simulation with multi-product formulas

Kaoru Mizuta

A multi-product formula (MPF) is a promising approach for Hamiltonian simulation efficiently both in the system size N and the inverse allowable error 1 / ε by combining Trotterization and the linear combination of unitaries (LCU). It achieves poly-logarithmic cost in 1 / ε like LCU [G. H. Low, V. Kliuchnikov, N. Wiebe, (2019)]. The efficiency in N is expected to come from the commutator scaling in Trotterization, and this appears to be confirmed by the error bound of MPF expressed by nested commutators [J. Aftab, D. An, K. Trivisa, (2024)]. However, we point out that the efficiency of MPF in the system size N is not exactly resolved yet in that the present error bound expressed by nested commutators is incompatible with the size-efficient complexity reflecting the commutator scaling. The problem is that q -fold nested commutators with arbitrarily large q are involved in their requirement and error bound. The benefit of commutator scaling by locality is absent, and the cost efficient in N becomes prohibited in general. In this paper, we show an alternative commutator-scaling error of MPF and derive its size-efficient cost properly inheriting the advantage in Trotterization. The requirement and the error bound in our analysis, derived by techniques from the Floquet-Magnus expansion, have a certain truncation order in the nested commutators and can fully exploit the locality. We prove that Hamiltonian simulation by MPF certainly achieves the cost whose system-size dependence is as large as Trotterization while keeping the p o l y l o g ( 1 / ε ) -scaling like the LCU. Our results will provide improved or accurate error and cost also for various algorithms using interpolation or extrapolation of Trotterization.

arXiv:2507.06557•Quantum•Jan 19, 2026•7 citations

Theory of Trotter Errors for Time-Dependent Product and Multi-product Formulas

Anonymous, Tatsuhiko N. Ikeda, Keisuke Fujii

Product formula (PF), which approximates the time evolution under a many-body Hamiltonian by the product of local time-evolution operators, is one of the central approaches for simulating quantum dynamics by quantum computers. It has been of great interest whether the errors of PFs can be expressed by commutators among local terms, since it brings the substantial suppression of the computational cost in the system size reflecting the locality of Hamiltonians. Although recent studies have revealed such error bounds for generic time-independent systems, it remains to be a difficult problem for time-dependent Hamiltonians except for low-order PFs. In this paper, we derive an error bound of generic PFs for smooth time-dependent Hamiltonians, which is expressed explicitly by nested commutators and their time derivatives. It indicates the substantial error suppression in the system size for generic local Hamiltonians, thereby giving a much better estimate of gate counts. Our derivation employs Floquet theory originally developed for time-periodic systems, with which we analyze the time-dependent PF errors by mapping them to those for time-independent PFs defined on an infinite-dimensional space. This approach is also applicable to a family of time-dependent PFs, such as the one for non-unitary dynamics. In particular, we clarify the error bound of a time-dependent multi-product formula, with which we can achieve exponentially better scaling with respect to the target accuracy than the PF. Our results will shed light on applications of near-term and future quantum computers, ranging from quantum simulation of nonequilibrium materials to faster algorithms exploiting time-dependent Hamiltonians such as adiabatic state preparation.

arXiv:2410.14243•PRX Quantum•Aug 4, 2026•13 citations

Trotter error bounds and dynamic multi-product formulas for Hamiltonian simulation

Sergiy M. Zhuk, Niall Robertson, Sergey B. Bravyi

Multi-product formulas (MPFs) are linear combinations of Trotter circuits offering high-quality simulation of Hamiltonian time evolution with fewer Trotter steps. Here we report two contributions aimed at making multi-product formulas more viable for near-term quantum simulations. First, we extend the theory of Trotter error with commutator scaling developed by Childs [A. M. Childs , ] to multi-product formulas. Our result implies that multi-product formulas can achieve a quadratic reduction of Trotter error in 1-norm (nuclear norm) on arbitrary time intervals compared with the regular product formulas without increasing the required circuit depth or qubit connectivity. The number of circuit repetitions grows only by a constant factor. Second, we introduce dynamic multi-product formulas with time-dependent coefficients chosen to minimize a certain efficiently computable proxy for the Trotter error. We use a minimax estimation method to make dynamic multi-product formulas robust to uncertainty from algorithmic errors, sampling, and hardware noise. We call this method the minimax MPF and we provide a rigorous bound on its error. Published by the American Physical Society 2024

arXiv:2306.12569•Physical Review Research•Sep 17, 2024•45 citations

Efficient and practical Hamiltonian simulation from time-dependent product formulas

Jan Lukas Bosse, Andrew M. Childs, Charles Derby +3 more

In this work we propose an approach for implementing time-evolution of a quantum system using product formulas. The quantum algorithms we develop have provably better scaling (in terms of gate complexity and circuit depth) than a naive application of well-known Trotter formulas, for systems where the evolution is determined by a Hamiltonian with different energy scales (i.e., one part is "large" and another part is "small"). Our algorithms generate a decomposition of the evolution operator into a product of simple unitaries that are directly implementable on a quantum computer. Although the theoretical scaling is suboptimal compared with state-of-the-art algorithms (e.g., quantum signal processing), the performance of the algorithms we propose is highly competitive in practice. We illustrate this via extensive numerical simulations for several models. For instance, in the strong-field regime of the 1D transverse-field Ising model, our algorithms achieve an improvement of one order of magnitude in both the system size and evolution time that can be simulated with a fixed budget of 1000 arbitrary 2-qubit gates, compared with standard Trotter formulas.

arXiv:2403.08729•Nature Communications•Mar 26, 2025•29 citations

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

Zohreh Davoudi, Jesse R. Stryker

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.

hep-latCross-listedarXiv:2608.21258•Aug 24, 2026•3 citations
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.
The well-conditioned multi-product formula (MPF), proposed by Low-Kliuchnikov-Wiebe (2019), is a high-order, time-independent Hamiltonian simulation algorithm that implements a linear combination of low-order product formulas. Prior work established its well-conditioned algorithmic construction and near-optimal time and precision dependence, but did not simultaneously provide an explicit error bound in terms of nested commutators, which has left its practical advantage uncertain. In this work, we provide a rigorous complexity analysis of the well-conditioned MPF, explicitly establishing both commutator scaling and near-optimal dependence on time and precision through a rigorous Baker-Campbell-Hausdorff (BCH) and variation-of-parameters-based error analysis. Using our improved complexity estimates, we present several physically relevant applications where the second-order-based MPF asymptotically outperforms the second-order product formula in all three aspects of system size, time, and precision. We further demonstrate that, while MPF yields worse scalings than the best post-Trotter methods in most applications, there exist certain parameter regimes in the nonlocal fast-transform Bogoliubov-de Gennes model where MPF can outperform both leading post-Trotter methods and product formulas with fixed or adaptively optimized order.
A multi-product formula (MPF) is a promising approach for Hamiltonian simulation efficiently both in the system size N and the inverse allowable error 1 / ε by combining Trotterization and the linear combination of unitaries (LCU). It achieves poly-logarithmic cost in 1 / ε like LCU [G. H. Low, V. Kliuchnikov, N. Wiebe, (2019)]. The efficiency in N is expected to come from the commutator scaling in Trotterization, and this appears to be confirmed by the error bound of MPF expressed by nested commutators [J. Aftab, D. An, K. Trivisa, (2024)]. However, we point out that the efficiency of MPF in the system size N is not exactly resolved yet in that the present error bound expressed by nested commutators is incompatible with the size-efficient complexity reflecting the commutator scaling. The problem is that q -fold nested commutators with arbitrarily large q are involved in their requirement and error bound. The benefit of commutator scaling by locality is absent, and the cost efficient in N becomes prohibited in general. In this paper, we show an alternative commutator-scaling error of MPF and derive its size-efficient cost properly inheriting the advantage in Trotterization. The requirement and the error bound in our analysis, derived by techniques from the Floquet-Magnus expansion, have a certain truncation order in the nested commutators and can fully exploit the locality. We prove that Hamiltonian simulation by MPF certainly achieves the cost whose system-size dependence is as large as Trotterization while keeping the p o l y l o g ( 1 / ε ) -scaling like the LCU. Our results will provide improved or accurate error and cost also for various algorithms using interpolation or extrapolation of Trotterization.
Product formula (PF), which approximates the time evolution under a many-body Hamiltonian by the product of local time-evolution operators, is one of the central approaches for simulating quantum dynamics by quantum computers. It has been of great interest whether the errors of PFs can be expressed by commutators among local terms, since it brings the substantial suppression of the computational cost in the system size reflecting the locality of Hamiltonians. Although recent studies have revealed such error bounds for generic time-independent systems, it remains to be a difficult problem for time-dependent Hamiltonians except for low-order PFs. In this paper, we derive an error bound of generic PFs for smooth time-dependent Hamiltonians, which is expressed explicitly by nested commutators and their time derivatives. It indicates the substantial error suppression in the system size for generic local Hamiltonians, thereby giving a much better estimate of gate counts. Our derivation employs Floquet theory originally developed for time-periodic systems, with which we analyze the time-dependent PF errors by mapping them to those for time-independent PFs defined on an infinite-dimensional space. This approach is also applicable to a family of time-dependent PFs, such as the one for non-unitary dynamics. In particular, we clarify the error bound of a time-dependent multi-product formula, with which we can achieve exponentially better scaling with respect to the target accuracy than the PF. Our results will shed light on applications of near-term and future quantum computers, ranging from quantum simulation of nonequilibrium materials to faster algorithms exploiting time-dependent Hamiltonians such as adiabatic state preparation.
Multi-product formulas (MPFs) are linear combinations of Trotter circuits offering high-quality simulation of Hamiltonian time evolution with fewer Trotter steps. Here we report two contributions aimed at making multi-product formulas more viable for near-term quantum simulations. First, we extend the theory of Trotter error with commutator scaling developed by Childs [A. M. Childs , ] to multi-product formulas. Our result implies that multi-product formulas can achieve a quadratic reduction of Trotter error in 1-norm (nuclear norm) on arbitrary time intervals compared with the regular product formulas without increasing the required circuit depth or qubit connectivity. The number of circuit repetitions grows only by a constant factor. Second, we introduce dynamic multi-product formulas with time-dependent coefficients chosen to minimize a certain efficiently computable proxy for the Trotter error. We use a minimax estimation method to make dynamic multi-product formulas robust to uncertainty from algorithmic errors, sampling, and hardware noise. We call this method the minimax MPF and we provide a rigorous bound on its error. Published by the American Physical Society 2024
In this work we propose an approach for implementing time-evolution of a quantum system using product formulas. The quantum algorithms we develop have provably better scaling (in terms of gate complexity and circuit depth) than a naive application of well-known Trotter formulas, for systems where the evolution is determined by a Hamiltonian with different energy scales (i.e., one part is "large" and another part is "small"). Our algorithms generate a decomposition of the evolution operator into a product of simple unitaries that are directly implementable on a quantum computer. Although the theoretical scaling is suboptimal compared with state-of-the-art algorithms (e.g., quantum signal processing), the performance of the algorithms we propose is highly competitive in practice. We illustrate this via extensive numerical simulations for several models. For instance, in the strong-field regime of the 1D transverse-field Ising model, our algorithms achieve an improvement of one order of magnitude in both the system size and evolution time that can be simulated with a fixed budget of 1000 arbitrary 2-qubit gates, compared with standard Trotter formulas.
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.