Source-linked AI summary
Nearly optimal lattice simulation by product formulas
Andrew M. Childs, Yuan Su
TL;DR
The paper addresses the incorrect system-size dependence produced by direct Taylor expansion of product-formula error. It develops a simplified local error representation and shows that product formulas achieve the stated lattice-simulation scaling while remaining attractive for near-term simulation.
Problem
Direct Taylor expansion of the product-formula error gives the correct time dependence but an incorrect dependence on n.
Method
The paper introduces an auxiliary operator and rewrites the error integrand using nested commutators with unitary conjugations.
Results
For constant s, p, and u, the product-formula error scales as O(nt^(p+1)).
Takeaways & Limitations
Product formulas provide an ancilla-free approach to lattice simulation, and their pure implementation can have a better constant prefactor than HHKL.
Abstract
from arXiv · showhide
We consider simulating an $n$-qubit Hamiltonian with nearest-neighbor interactions evolving for time $t$ on a quantum computer. We show that this simulation has gate complexity $(nt)^{1+o(1)}$ using product formulas, a straightforward approach that has been demonstrated by several experimental groups. While it is reasonable to expect this complexity---in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill---we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and further simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.
Nearly optimal lattice simulation by product formulas – Supplementary
The supplementary material identifies the paper, its authors, and its date.
- The authors are Andrew M. Childs and Yuan Su.
- The document is dated December 17, 2019.
I. NONRIGOROUS ERROR ANALYSIS BY BAKER-CAMPBELL-HAUSDORFF FORMULA
The BCH-based analysis recovers the desired first-order time scaling but fails to establish the required system-size dependence rigorously when higher-order nested commutators are considered.
- The BCH approach is difficult to formalize because higher-order Taylor terms require bounding nested commutators.
- The lattice Hamiltonian is partitioned into odd and even nearest-neighbor terms before applying the first-order product formula.
- The truncated BCH expansion yields the desired first-order error scaling, but this conclusion ignores higher-order terms.
- When the nesting depth exceeds n, the commutator estimate becomes O(n^p t^p), producing superlinear n-dependence.
- Local error analysis replaces the problematic expansion with a fully rigorous error expression and extends to higher-order formulas.
II. CANONICAL PRODUCT FORMULAS AND ORDER CONDITIONS
The paper introduces canonical product formulas and equivalent order conditions that organize the analysis of Lie-Trotter-Suzuki constructions.
- Canonical formulas include Lie-Trotter and Suzuki constructions, including the second-order and (2k)th-order examples.
- A canonical product formula represents H = A + B as a sequence of exponentials with real coefficients a_j and b_j.
- The parameter s counts stages, while u bounds the absolute values of all formula coefficients.
- A formula has order p when its error vanishes as O(t^(p+1)), equivalently when its first p derivatives satisfy the stated zero conditions.
- Theorem 1 shows that the product-formula order, derivative conditions, and auxiliary-function conditions are equivalent.
III. SIMPLIFIED LOCAL ERROR REPRESENTATION
The simplified local error representation rewrites product-formula error through an auxiliary operator and nested commutators, yielding the correct system-size scaling for higher-order formulas.
- The product-formula error is represented by an integral involving the auxiliary operator T(t) = S(t)†R(t).
- Direct Taylor expansion of R(t) gives incorrect n-dependence, motivating the auxiliary operator and a new integrand representation.
- The new integrand is a linear combination of nested commutators with unitary conjugations, using numbers of summands and layers independent of n and t.
- Theorem 2 provides the simplified local error representation for canonical product formulas.
- For a pth-order formula with constant s, p, and u, the product-formula error scales as O(nt^(p+1)).
IV. ADJOINT MAPPINGS AND ANALYSIS OF THE pTH-ORDER ALGORITHM
This section analyzes the pth-order product-formula algorithm for lattice simulation using adjoint mappings to bound its error.
- The analysis introduces adjoint mappings for the pth-order product-formula algorithm.
- The adjoint-mapping framework is used to obtain a bound on product-formula error.
- The section organizes the analysis into defining adjoint mappings and deriving the resulting error bound.
A. Adjoint mappings
The section defines adjoint and commutator transformations and develops differentiation rules, including an abbreviated representation that tracks time variables rather than operators.
- Ad_X is defined as the conjugation transformation associated with an invertible matrix X.
- ad_X is defined as the commutator transformation for an arbitrary operator X.
- Differentiation rules for Ad and ad support Taylor-expansion calculations for operator-valued functions.
- The abbreviated adjoint representation omits operator information and retains only the time variables τ1, . . . , τm.
- A proposition establishes a differentiation rule for the abbreviated adjoint representation, with its proof based on separating time variables and applying the multi-factor Leibniz rule.
B. Error analysis of the pth-order algorithm
The error analysis represents product-formula error through integrals and bounds nested commutators using locality, yielding linear system-size scaling at fixed order and interaction strength.
- The ideal evolution for H = A + B is E(t) = e^-it(A+B), while a higher-order product formula provides an approximation S(t).
- The Taylor-expansion analysis shows that terms of order p−1 or less vanish, leaving an order-p integral remainder.
- The nested-commutator analysis bounds the number of nonzero terms by (2k−1)^p.
- Locality bounds the support growth of nested commutators, with support increasing by two under each relevant adjoint composition.
- O(nt^(p+1)) is the product-formula error scaling when s, p, and u are constant.
V. TIME-DEPENDENT PRODUCT FORMULAS AND LOCAL ERROR ANALYSIS
This section extends product-formula analysis to time-dependent Hamiltonians by introducing canonical formulas, order conditions, and a time-dependent local-error analysis.
- The appendix analyzes time-dependent product formulas and their local error structure.
- Canonical formulas for time-dependent Hamiltonian simulation are introduced and their order conditions are studied.
- The section then analyzes the local error structure for time-dependent simulation.
A. Time-dependent canonical formulas and order conditions
The paper develops time-dependent canonical product formulas and equivalent order conditions for approximating Hamiltonian evolution. The framework assumes infinitely differentiable Hamiltonian terms, while noting that this assumption can be relaxed.
- Scope: The presentation assumes infinite differentiability of H(t) and its terms to ensure the stated approximation order, although the assumption may be relaxed.The assumption is imposed primarily to simplify the presentation.
- Evolution derivatives: The time-ordered evolution operator is infinitely differentiable when the Hamiltonian is infinitely differentiable, with higher derivatives characterized recursively.The recursive operators T_j(t) support the analysis of higher-order approximation conditions.
- Canonical product formulas: Time-dependent canonical product formulas sample A(t) and B(t) at specified times and apply staged exponentials to approximate the ideal evolution.Each stage uses real coefficients and evaluates the Hamiltonian terms at times tα_k and tβ_k.
- Order conditions: The analysis defines product-formula order through matching derivatives at t=0 up to the chosen order p.This derivative-matching condition is connected to equivalent residual formulations involving operator-valued functions.
- Order conditions: Four conditions for a pth-order time-dependent canonical formula are shown to be equivalent, including derivative matching and vanishing derivatives of residual functions.The theorem unifies these formulations for H(t)=A(t)+B(t) with infinitely differentiable terms.
B. Time-dependent local error representation
The paper derives an integral representation for the error of time-dependent canonical product formulas. For pth-order formulas, the representation exposes the approximation error through the local residual and order conditions.
- Residual construction: The local residual is formed from the derivative of the product formula and the Schrödinger generator, then transformed by unitary conjugation.This transformation produces an operator-valued function used to represent the global product-formula error.
- Derivation: The derivation uses a chain rule for differentiating operator exponentials and unitary conjugation of the staged product formula.These steps connect the canonical stages to the residual representation.
- Local error representation: The error between a time-dependent canonical product formula and the ideal time-ordered evolution admits an integral representation.The formula applies to staged canonical products whose coefficients and sampling times define the approximation.
- Order dependence: For a time-dependent pth-order formula, the error representation incorporates the order conditions through Taylor expansion with an integral remainder.The resulting expression provides the stated order-dependent error scaling.
VI. EMPIRICAL PERFORMANCE
The empirical study compares product-formula simulation with HHKL and evaluates ordering choices for first-order formulas. It finds that pure product formulas have a better practical prefactor, while even-odd ordering performs better than X-Y-Z ordering.
- Gate-count comparison: The study compares empirical gate counts for HHKL with fourth-order product-formula blocks against the pure fourth-order product-formula algorithm.The pure method simulates the original lattice Hamiltonian, whereas HHKL decomposes the evolution into blocks.
- Benchmark setup: The one-dimensional benchmark uses a nearest-neighbor Heisenberg model with a random magnetic field, open boundaries, accuracy ϵ=10^-3, and t=n.The Hamiltonian is normalized before empirical gate complexity is estimated.
- Gate-count comparison: Although HHKL has better asymptotic scaling, the pure product-formula approach has a significantly better constant prefactor in the comparison.HHKL adds negative Hamiltonian terms to compensate for Lieb-Robinson decomposition error and incurs overhead when simulating blocks.
- Ordering comparison: Both even-odd and X-Y-Z orderings are consistent with the upper bound r=O(nt^2)=O(n^3), but even-odd ordering performs better empirically.The comparison uses first-order product formulas and empirical values of r.