The Linear Combination of Hamiltonian Simulation (LCHS) framework simulates dissipative linear dynamics by representing time evolution as an integral over unitary operators, which is discretized by quadrature and implemented via Hamiltonian simulation. While existing analyses achieve near-optimal scaling in time and precision using norm-based quantities of the dissipative generator, we show that implementing the Hamiltonian simulation steps with Multi-Product Formulas (MPFs) yields commutator-sensitive error and complexity bounds. We demonstrate that the quadrature rule affects not only discretization error but also commutator structure and query complexity. This dependence is quantified through post-quadrature analysis for abstract MPF error profiles and for general time-independent and local Hamiltonians using known commutator-sensitive MPF error estimates. We compare uniform trapezoidal and free-scale sinh--sinh quadrature, showing improved quadrature-cardinality scaling for the latter, and illustrate the framework with applications to fractional diffusion, advection--diffusion, and open quantum systems.
The Linear Combination of Hamiltonian Simulation (LCHS) framework simulates dissipative linear dynamics by representing time evolution as an integral over unitary operators, which is discretized by quadrature and implemented via Hamiltonian simulation. While existing analyses achieve near-optimal scaling in time and precision using norm-based quantities of the dissipative generator, we show that implementing the Hamiltonian simulation steps with Multi-Product Formulas (MPFs) yields commutator-sensitive error and complexity bounds. We demonstrate that the quadrature rule affects not only discretization error but also commutator structure and query complexity. This dependence is quantified through post-quadrature analysis for abstract MPF error profiles and for general time-independent and local Hamiltonians using known commutator-sensitive MPF error estimates. We compare uniform trapezoidal and free-scale sinh--sinh quadrature, showing improved quadrature-cardinality scaling for the latter, and illustrate the framework with applications to fractional diffusion, advection--diffusion, and open quantum systems.
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.
Linear combination of Hamiltonian simulation (LCHS) provides an asymptotically optimal framework for the quantum simulation of linear non-unitary dynamics. The LCHS approach approximately implements the Peano--Baker propagator through an integral representation determined by a kernel function. We establish an LCHS approximation theorem for a broadened class of admissible kernel functions, defined by natural complex-analytic conditions. In the standard time-independent block-encoding access model, we explicitly construct, for each target error ε, the unique kernel function in this class minimizing the query-cost functional and show that the minimum of this functional has the asymptotic expansion π2e(logε1−loglogε1+o(1)) as ε↓0. The provably optimal leading coefficient 2e/π improves by a factor of approximately 2.1 on the coefficient obtained empirically by Low and Somma through numerical minimization over their family of optimally scaling kernel functions. We construct a spectrally convergent quadrature with explicit bounds on operator error and linear combination of unitaries (LCU) subnormalization, proving that this asymptotic improvement persists after discretization into a finite linear combination of unitaries suitable for implementation. Our results are based on Hardy space theory and convex analysis.
Linear combination of Hamiltonian simulation (LCHS) provides an efficient method for implementing matrix exponentials e−tA on quantum computers. In this paper, we develop LCHS formulas for computing general matrix functions f(A) when f is analytic on the numerical range of A, with A possibly non-normal. The essential technical tool is Weyl calculus, which reduces the construction of LCHS formulas for noncommuting operators to scalar Fourier approximation problems. Our construction yields a quantum eigenvalue transformation algorithm with optimal O(logε1) query complexity scaling. Furthermore, our Weyl-calculus-based theory gives rise to an ansatz-free convex optimization framework that directly produces discrete LCHS formulas. This circumvents the inefficiencies of traditional quadrature rules and yields formulas highly optimized for coherent implementation on quantum computers. In addition, both our theory and optimization framework apply to the simulation of time-dependent dissipative ODE dtdψ(t)=−A(t)ψ(t), for which we achieve a 2.1× cost reduction over prior art.
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
We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an s-sparse Hermitian matrix with row and column Euclidean norms bounded by η, evolution for time t to error ε uses O(sτ+sτlog(1/ε)+log(1/ε)) queries, where τ=η∣t∣. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in sτ and log(1/ε). For dissipative linear differential equations we obtain O(gˉ[s(τ+τ)+1]log(Cgˉ/ε)) queries, where τ is the evolution time multiplied by a norm bound, gˉ bounds the ratio of combined input and source norms to the final-solution norm, and C is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give O(κslog(1/ε)) queries when ∥A∥≤1 and ∥A−1∥≤κ, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.