PaperlayerView exact revision on arXiv

Source-linked AI summary

Time-dependent Hamiltonian simulation with $L^1$-norm scaling

Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, Nathan Wiebe

arXiv:1906.07115v2quant-phcond-mat.str-elcs.DSphysics.chem-ph

TL;DR

Time-dependent Hamiltonian simulation has lacked the expected complexity scaling with the Hamiltonian’s integrated norm, despite that norm reflecting its instantaneous size. The paper develops sampling- and rescaling-based algorithms that achieve this scaling, yielding a polynomial speedup in norm dependence and potential practical advantages for molecular scattering.

  • Problem

    Prior time-dependent simulation analyses scale with t max_τ ||H(τ)|| rather than the integrated norm ∫_0^t ||H(τ)|| dτ, leaving open whether algorithms can exploit the latter.

    Source: §1 · p. 3

  • Method

    The paper introduces continuous sampling of time-dependent Hamiltonians and a Schrödinger-equation rescaling principle used to improve the Dyson-series approach.

    Source: §1 · p. 4, §6 · p. 31

  • Results

    The algorithms achieve L1-norm scaling, a polynomial speedup in norm dependence over previous simulation scaling.

    Source: §6 · p. 31

  • Takeaways & Limitations

    The norm-based improvement can be favorable in practice for semi-classical molecular scattering, while continuous qDRIFT may be better suited to near-term simulation.

    Source: §6 · pp. 31–32

    The analysis focuses on sparse-matrix and LCU input models and gate complexity, ignoring the cost of implementing the coefficient oracle.

    Source: §1 · p. 4

Abstract

from arXiv · show

The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For sparse Hamiltonian simulation, the gate complexity scales with the $L^1$ norm $\int_{0}^{t}\mathrm{d}\tau\left\lVert H(\tau)\right\lVert_{\max}$, whereas the best previous results scale with $t\max_{\tau\in[0,t]}\left\lVert H(\tau)\right\lVert_{\max}$. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schr\"{o}dinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. These algorithms could potentially be applied to semi-classical simulations of scattering processes in quantum chemistry.

1 Introduction

Time-dependent Hamiltonian simulation is harder to analyze than stationary evolution, and previous algorithms did not achieve the intuitive scaling with the Hamiltonian’s instantaneous norm. The introduction presents two approaches to obtain integrated-norm scaling and identifies molecular scattering as a potential application.

1 Introduction

  • Earlier time-dependent simulation approaches include higher-order product formulas with smoothness assumptions, Hamiltonian averaging, fractional queries, and truncated Dyson series.The product-formula smoothness assumption was relaxed in subsequent work using Hamiltonian averaging and Monte Carlo estimation.Source: §1 · p. 3
  • The algorithms achieve gate complexity scaling with ∫_0^t ||H(τ)|| dτ rather than the best previous scaling, t max_τ ||H(τ)||; the inequality is not generally saturated, yielding a strict speedup.The improvement is identified for sparse Hamiltonian simulation, with analogous results for linear combinations of unitaries.Source: §1 · p. 4
  • The work studies sparse-matrix and linear-combination-of-unitaries input models, focusing mainly on gate complexity and excluding coefficient-oracle implementation cost.The sparse-matrix model provides oracles for nonzero matrix locations and values; the LCU model assumes classically computable coefficients and controllable summands.Source: §1 · p. 4
  • Continuous qDRIFT samples times with probability favoring larger ||H(τ)||, then evolves under the sampled time-independent Hamiltonian; it is universal relative to the discrete qDRIFT scheme [13].The analysis also shaves a multiplicative factor by evaluating how evolution changes with Hamiltonian rescaling.Source: §1 · p. 4
  • A rescaling principle makes the time-dependent Hamiltonian’s norm constant, enabling a truncated Dyson-series algorithm with L1-norm scaling.The introduction presents this as an improvement to prior Dyson-series simulation approaches [8] [29] [36].Source: §1 · pp. 4–5
  • Semi-classical scattering of molecules in chemical reactions is a target application because the Hamiltonian norm varies dramatically and its L1 norm can be much smaller than its L∞ norm.The authors identify this as a setting where the improvement can be advantageous.Source: §1 · p. 5

2 Preliminaries

This section establishes time-ordered evolution, norm and input-model conventions, and L1-norm scaling, including an analysis of L1-scaling query complexity for the sparse fractional-query approach. It also introduces continuous qDRIFT sampling and Schrödinger-equation rescaling for achieving L1-norm scaling in both query and gate complexity.

2.1 Time-dependent Hamiltonian evolution

  • Under the default continuously differentiable, everywhere-nonzero assumption, general time-dependent evolution is represented by a time-ordered exponential, and Lemma 1 bounds distances between such evolutions.For time-independent Hamiltonians, evolution instead has the closed form e^(-itH).Source: §2.1 · p. 5

2.2 Notation for norms

  • The notation distinguishes vector ℓp, matrix Schatten p, and function Lp norms, while simulation errors may be measured in spectral or diamond norm, with conversion losing at most a factor of 2.For operator-valued functions, the pointwise Schatten norm is followed by an Lq norm over time.Source: §2.2 · pp. 6–7

2.3 Hamiltonian input models

  • The standard input models are d-sparse matrices with time-independent nonzero locations and LCU decompositions with nonnegative differentiable coefficients and Hermitian unitaries.The qDRIFT protocol can also use continuous, nonzero Hermitian-valued terms that can be efficiently exponentiated.Source: §2.3 · pp. 7–8

2.4 Simulation algorithms with L1-norm scaling

  • L1-norm scaling means complexity depends on the time integral of an upper bound on the instantaneous max norm in the SM model, or coefficient bounds in the LCU model.The bounds and auxiliary information must be accessible to the algorithm; the paper expresses complexity using the corresponding norms of the original Hamiltonian or coefficient vector.Source: §2.4 · p. 9

2.5 Query complexity with L1-norm scaling

  • The sparse fractional-query analysis establishes L1-norm query scaling for simulating d-sparse time-dependent Hamiltonians using the Oloc and Oval oracles.The theorem states the result for simulations with accuracy ϵ; the supplied passages do not expose its full query-count expression.Source: §2.4 · p. 10, §2.5 · p. 11
  • The time-dependent Hamiltonian is encoded in an ancilla, and the fractional-query operators Uj increment the time register.The driving operations also need to update the index l, whose number of values depends on k.Source: §2.5 · pp. 12–13
  • The fractional-query algorithm achieves L1-norm scaling for query complexity, but does not directly provide a useful gate-complexity result.Its gate cost is hindered by implementing driving operations that update the time index k and the k-dependent index l, potentially requiring work proportional to the sum of η(k) over many k values.Source: §2.5 · p. 13
  • The proposed continuous qDRIFT sampling and Schrödinger-equation rescaling techniques achieve L1-norm scaling for both query and gate complexity.They are developed in Sections 3 and 4, respectively.Source: §2.5 · p. 13

3 Continuous qDRIFT

This section presents continuous qDRIFT as a classical-sampling approach to time-dependent Hamiltonian simulation, with error analysis based on the Hamiltonian’s L1 norm and an extension to the LC model through universality. It derives sparse-model and LCU simulation complexities under efficient-sampling assumptions.

3.1 A classical sampler of time-dependent Hamiltonians

  • The sampler draws a time τ and applies e^(-iH(τ)/p(τ)) to implement a unit-cost mixed-unitary channel; a finitely discontinuous spectral-norm upper bound can replace the exact norm.The protocol assumes efficient sampling from the chosen distribution; with the exact norm, p(τ) = ∥H(τ)∥∞/∥H∥∞,1.Source: §3.1 · p. 14
  • Continuous qDRIFT has short- and long-time error bounds that depend on the Hamiltonian’s L1 norm; long-time simulation uses variable-time segmentation.The short-time bound is useful only when its right-hand side is less than 1.Source: §3.1 · pp. 14, 15, 18

3.2 Universality

  • Continuous qDRIFT extends to the LC model: a universal correspondence lets its L1-error analysis apply to time-dependent Hamiltonians that are sums of terms.The short-time LC bound tightens Campbell’s bound by a multiplicative factor from a tail bound.Source: §3.2 · pp. 19–21
  • For continuous, everywhere-nonzero Hamiltonian components, continuous qDRIFT approximates the time-ordered evolution channel using component-norm sampling and a suitable time division.The error condition is met by choosing the number of divisions sufficiently large.Source: §3.2 · pp. 22–23

3.3 Complexity of the continuous qDRIFT algorithm

  • The sparse-model corollary gives L1-norm-scaled query and gate complexities, assuming the stated distribution over sparse terms can be sampled efficiently.The stated sampling distribution uses the Hamiltonian's maximum-entry norm and sparsity d.Source: §3.3 · p. 23
  • The LCU corollary gives an L1-norm-scaled gate complexity when controlled term exponentiation costs ge gates and the coefficient-weighted distribution can be sampled efficiently.The sampling distribution is pl(τ) = αl(τ)/∥α∥1,1.Source: §3.3 · p. 24

4 Rescaled Dyson-series algorithm

The rescaled Dyson-series algorithm adapts the Schrödinger equation so simulation can use L1-norm scaling. The section develops the rescaling principle and applies it to sparse-matrix and LCU Hamiltonian inputs.

4.1 A rescaling principle for the Schrödinger equation

  • Rescaling the evolution time and Hamiltonian produces a constant-norm Hamiltonian with the same time-evolution operator, enabling L1-norm scaling.An algorithm whose complexity scales with the rescaled Hamiltonian’s L∞ norm can thereby simulate the original Hamiltonian with L1-norm scaling.Source: §4.1 · pp. 24–25

4.2 Complexity of the rescaled Dyson-series algorithm

  • The Dyson-series implementation requires additional oracle access for the inverse change of variable, unlike continuous qDRIFT’s classical access.The theorem statements also assume a suitable positive, continuously differentiable upper bound on the relevant norm.Source: §4.2 · pp. 25–26
  • The rescaled Dyson-series algorithm provides L1-norm-scaled simulation for sparse-matrix and LCU Hamiltonians.The section states this result for the SM model and then turns to the LCU model.Source: §4.2 · pp. 26, 28

5 Applications to chemistry and scattering theory

The section models semi-classical molecular scattering by treating nuclei classically and simulating the electronic dynamics under a time-dependent Hamiltonian. A helium collision illustrates how a brief interaction can sharply change the Hamiltonian norm.

5 Applications to chemistry and scattering theory

  • The Ehrenfest and time-dependent self-consistent field approximations treat nuclear positions as classical trajectories while the electronic dynamics obey a Schrödinger equation.The stated justification is that the nuclear mass is substantially greater than the electronic mass and that a sufficiently narrow wave packet’s centroid follows a classical trajectory to leading order in ℏ.Source: §5 · p. 30
  • Under these approximations, the electronic dynamics become a standard second-quantized chemistry simulation with a time-dependent Hamiltonian.The passage notes that extending the formulation to multiple nuclei replaces a sum over two nuclear positions with a sum over all L positions.Source: §5 · pp. 30–31
  • The example models two helium nuclei with a Lennard-Jones potential, using an initial separation of 20 nm and velocity of 1350 m/s.The potential parameters are given as ϵ ≈ 10 K and r_m ≈ 2.6 Å, with the initial radial velocity set approximately to helium’s RMS velocity at 25 °C.Source: Figure 1 · p. 31, §5 · p. 31
  • The collision produces a brief, intense interaction, so the Hamiltonian norm changes dramatically and L1-norm-scaled algorithms are expected to be advantageous.The authors leave a detailed study of the advantage for future work.Source: §5 · p. 31

6 Discussion

The discussion presents L1-norm scaling for time-dependent Hamiltonian simulation and describes its near-optimality, practical trade-offs, and scope. It also identifies open questions about higher-order sampling and rescaling other algorithms.

6 Discussion

  • The algorithms achieve complexity scaling with the integrated Hamiltonian norm, and the discussion describes this as a polynomial speedup in norm dependence.The paper says the L1 dependence matches the intuition that simulation difficulty depends on the Hamiltonian norm instantaneously.Source: §6 · p. 31
  • The L1-norm dependence may not be significantly improvable, while knowing the initial state’s energy range could permit further speedup.The discussion attributes the former suggestion to the instantaneous-norm interpretation and cites [34] [43] for the latter possibility.Source: §6 · p. 31
  • The rescaled Dyson-series approach matches the lower-bound dependence on d∥H∥max t and ϵ, except that it multiplies rather than adds those terms.The paper notes that this product dependence does not achieve the optimal tradeoff between time and precision.Source: §6 · pp. 31–32
  • The rescaled Dyson-series method requires computing the rescaling function and Hamiltonian norm in superposition, while continuous qDRIFT uses classical sampling and may suit near-term simulation better.Continuous qDRIFT’s complexity also has no dependence on L in the LCU decomposition.Source: §6 · p. 32
  • The Dyson-series analysis extends to finitely many discontinuities by dividing the evolution into segments, while continuous qDRIFT requires only Lebesgue integrability.For the Dyson-series approach, concatenating segments preserves L1-norm scaling.Source: §6 · p. 32
  • Continuous qDRIFT achieves only first-order accuracy, and the authors leave open whether a higher-order protocol can be found or ruled out.They mention more complicated sampling as a possible direction.Source: §6 · pp. 32–33
  • The rescaling principle may apply to other simulation algorithms, but a larger derivative of the rescaled Hamiltonian can make an algorithm perform worse.The discussion specifically raises using product formulas on the rescaled Hamiltonian and leaves a thorough study for future work.Source: §6 · p. 33

A Continuous qDRIFT and Hamiltonian averaging

This section contrasts continuous qDRIFT with a prior Hamiltonian-averaging approach. The central distinction is that continuous qDRIFT samples times with a probability distribution biased toward larger instantaneous Hamiltonian norms.

A Continuous qDRIFT and Hamiltonian averaging

  • The averaging approach of [42] uses uniform random times, so its complexity scales with the L∞ norm rather than the L1 norm.The section says this limitation cannot be fixed merely by improving the analysis of that same algorithm.Source: A Continuous qDRIFT and Hamiltonian… · pp. 37–38
  • Continuous qDRIFT biases its sampling toward times with larger instantaneous norms and directly simulates the time-dependent Hamiltonian with L1-norm scaling.The section contrasts this with the uniform-time sampling used in [42].Source: A Continuous qDRIFT and Hamiltonian… · pp. 37–38
  • The authors show that continuous qDRIFT can simulate the average Hamiltonian with L1-norm scaling, and conclude that it supersedes the Monte Carlo estimation approach of [42].Their comparison combines an improved error analysis for replacing the time-ordered evolution with average-Hamiltonian evolution and the qDRIFT simulation result.Source: A Continuous qDRIFT and Hamiltonian… · p. 38

A.1 Hamiltonian averaging

This section compares the exact time-ordered evolution with evolution under the average Hamiltonian. It states bounds on both spectral-norm and diamond-norm distance under continuity and nonzero-Hamiltonian assumptions.

A.1 Hamiltonian averaging

  • The proof compares the evolutions through their Schrödinger equations and uses telescoping and integral bounds.The argument distinguishes the generators over the intervals defining the two evolutions.Source: §A.1 · pp. 38–39
  • For a continuous, everywhere-nonzero Hamiltonian, Theorem 11 bounds the spectral-norm distance between the time-ordered evolution and evolution under the average Hamiltonian.The average Hamiltonian is denoted H_av in the theorem statement.Source: §A.1 · p. 39
  • Theorem 11′ states a corresponding bound on the diamond-norm distance between the time-ordered and average-Hamiltonian channels.It assumes the Hamiltonian is continuous and nonzero everywhere.Source: §A.1 · p. 39

A.2 Implementing Hamiltonian averaging by continuous qDRIFT

Continuous qDRIFT implements Hamiltonian averaging with L1-norm scaling, improving on the L∞-scaled algorithm of [42]. Theorem 12 also improves the constant prefactor from 8 to 4.

A.2 Implementing Hamiltonian averaging by continuous qDRIFT

  • Continuous qDRIFT implements Hamiltonian averaging with L1-norm scaling, improving on the L∞-scaled algorithm of [42].The section introduces this result for continuous, everywhere-nonzero time-dependent Hamiltonians.Source: §A.2 · p. 39
  • Theorem 12 improves the constant prefactor from 8 to 4.Source: §A.2 · p. 40
  • The proof parameterizes the averaged-evolution and continuous-qDRIFT channels so their first derivatives agree at u = 0, then applies the fundamental theorem of calculus twice.Source: §A.2 · p. 40

Related papers

Loading 1906.07115v2…