PaperlayerView exact revision on arXiv

Source-linked AI summary

Simulating Quantum Dynamics On A Quantum Computer

Nathan Wiebe, Dominic W. Berry, Peter Hoyer, Barry C. Sanders

arXiv:1011.3489v2quant-phmath-phmath.MP

TL;DR

Time-dependent Hamiltonian simulation needs methods that retain efficient time scaling when Hamiltonians vary over time. The paper presents constant- and adaptive-step algorithms for sparse, sufficiently smooth Hamiltonians, and shows near-linear scaling under stated conditions.

  • Problem

    Extending efficient Hamiltonian simulation to time-dependent cases is challenging when Hamiltonian behavior varies over time.

    Source: §I · p. 1, B. Adaptive time steps · p. 3

  • Method

    The paper applies high-order integrators to sparse time-dependent Hamiltonians and uses constant or adaptively chosen time steps.

    Source: §I · p. 1, §IX · p. 18

  • Results

    For sufficiently smooth terms, the algorithms can have query complexity similar to BACS, and the stated scaling can be nearly linear in average Υ times the evolution time.

    Source: §IV · p. 7, §IX · p. 18

  • Takeaways & Limitations

    Near-linear time scaling is achievable within the paper's stated smoothness and boundedness conditions.

    Source: §IV · p. 7

    When quantities such as Λ are difficult to compute, the output may not meet error tolerance; n and the oracle's upper bound for ∥Hµ∥ must be known.

    Source: §IX · p. 18

Abstract

from arXiv · show

We present efficient quantum algorithms for simulating time-dependent Hamiltonian evolution of general input states using an oracular model of a quantum computer. Our algorithms use either constant or adaptively chosen time steps and are significant because they are the first to have time-complexities that are comparable to the best known methods for simulating time-independent Hamiltonian evolution, given appropriate smoothness criteria on the Hamiltonian are satisfied. We provide a thorough cost analysis of these algorithms that considers discretizion errors in both the time and the representation of the Hamiltonian. In addition, we provide the first upper bounds for the error in Lie-Trotter-Suzuki approximations to unitary evolution operators, that use adaptively chosen time steps.

I. INTRODUCTION

The paper extends high-order product-formula methods to sparse, time-dependent Hamiltonians, targeting near-linear simulation-time complexity under smoothness conditions. It develops constant and adaptive time-step algorithms, with adaptive steps addressing intervals where Hamiltonian behavior varies sharply.

I. INTRODUCTION

  • The algorithms apply high-order integrators to sparse time-dependent Hamiltonians, whose complexity depends on the norms of H(t) and its derivatives.Adaptive steps can make complexity depend on average rather than maximum norm values, under additional restrictions.Source: §I · p. 1
  • Polar-form oracle outputs enable one-sparse exponentials to be implemented with a circuit using magnitude- and phase-proportional qubit rotations.The paper also accounts for errors from discretizing oracle times.Source: §I · p. 2

II. OUR APPROACH

  • The simulation starts from an encoded initial state and approximates the final state by applying an encoded approximation of the time-ordered exponential.The target approximation is specified in trace distance.Source: §II · p. 2

A. Constant-Sized Time Step Simulation

  • The constant-step method combines BACS sparse decomposition with higher-order integrators to target time-complexity scaling as ∆t^(1+o(1)).The BACS decomposition yields 6d^2 one-sparse Hamiltonians for sparseness parameter d.Source: A. Constant-Sized Time Step Simulation · p. 2
  • For sufficiently smooth Hamiltonians, the proposed time-dependent simulation has query complexity scaling as (Λ∆t)^(1+o(1)).The constant-step analysis uses an upper bound Λ on Hamiltonian derivative norms.Source: A. Constant-Sized Time Step Simulation · p. 3
  • The constant-step algorithm can omit derivative-discontinuity points and retain essentially unchanged complexity, provided the Hamiltonian norm is adequately bounded.This avoids integrating across points where the cited error bounds may not apply.Source: A. Constant-Sized Time Step Simulation · p. 3

B. Adaptive time steps

  • Adaptive steps vary interval lengths and product-formula order to avoid overly conservative steps when the Hamiltonian changes at different rates.The method chooses a sequence of simulation times rather than dividing the full interval into equal steps.Source: B. Adaptive time steps · p. 3
  • Adaptive complexity can depend on average Υ(t) rather than its maximum when Υ(t) changes sufficiently slowly, requiring a bound on its derivative.The step-size choice is based on Υ(t) at the beginning of each interval.Source: B. Adaptive time steps · pp. 3–4

C. Resource Analysis

The resource analysis specifies oracle encodings and accounts for both qubit use and time discretization. It also establishes that the simulation remains stable under time imprecision, subject to stated precision and discontinuity conditions.

C. Resource Analysis

  • Polar-form oracle outputs allow one-sparse evolution to use a circuit of qubit rotations proportional to each matrix element's magnitude and phase.The rotations can be performed independently for each precision qubit returned by the oracle.Source: C. Resource Analysis · p. 4
  • The number of qubits accessed for nonzero-element positions scales as n log*n, while value-query qubit use is independent of n and depends logarithmically on several simulation parameters.The listed parameters include error tolerance, evolution time, Hamiltonian sparseness, derivative norm, and k; dependence on k is not logarithmic.Source: C. Resource Analysis · p. 4
  • Time discretization can perturb Hamiltonian estimates and threaten higher-order product-formula error scaling, but the simulation is stable at sufficient precision.Required precision depends on k, d, ∆t, and the maximum derivative norm; for discontinuities, discretization must be no greater than the time between them.Source: C. Resource Analysis · p. 4

III. BACKGROUND AND DEFINITIONS

The background section represents Hamiltonians as sums of terms sparse in their own canonical bases, then decomposes sparse terms into one-sparse components for product-formula simulation. Smoothness conditions determine when approximation orders and error bounds apply.

III. BACKGROUND AND DEFINITIONS

  • A Hamiltonian may be expressed as a sum of terms sparse in their respective canonical bases, with basis transformations mapping to those bases.The decomposition supports expressing evolution through one-sparse Hamiltonians.Source: §III · p. 5
  • The BACS decomposition expresses a sparse Hamiltonian as a sum of 6d^2 one-sparse Hamiltonians, enabling product-formula evolution through one-sparse components.The oracle supplies locations and values of nonzero matrix elements used in the decomposition.Source: §III · p. 5
  • P-smoothness is required to achieve a given approximation order, while Λ-P-smoothness supplies derivative bounds for bounding error.For adaptive steps, the time-dependent derivative bound is the relevant quantity.Source: §III · p. 5
  • For short time intervals, approximation error is O((Λ∆t)^(2k+1)); for longer ∆t, dividing evolution into r subintervals and choosing r for error at most ε requires r = O((Λ∆t)^(1+1/2k)/ε^(1/2k)).Overall simulation complexity is proportional to r.Source: §III · p. 6

IV. RESULTS

The results bound adaptive-step simulation query cost and establish near-linear time scaling for sufficiently smooth Hamiltonians. The analysis also specifies precision conditions that keep round-off error within half the error tolerance.

Error and precision

  • The simulation error is divided between integrator error and round-off from finite-bit time and discretized Hamiltonian representations.The stated precision conditions ensure round-off contributes at most ǫ/2, leaving the other half for integrator error.Source: §IV · p. 6
  • The precision lemma bounds round-off error by ǫ/2 when the time and matrix-element precision requirements and subinterval-length condition are met.The supplied passages state that these conditions apply to products of evolutions over disjoint intervals.Source: §IV · pp. 6–7

Adaptive-step complexity

  • The adaptive-step theorem bounds oracle queries for d-sparse, pointwise-smooth Hamiltonians when the smoothness measure obeys a derivative bound.The theorem also requires precision conditions on the time and matrix-element representations.Source: §IV · p. 7
  • Sufficiently smooth, bounded Hamiltonians permit near-linear scaling with the average smoothness measure, which the paper identifies as nearly optimal.The paper states that linear scaling is a lower bound; its corollary applies when the Hamiltonian terms are sufficiently smooth and bounded on the stated interval.Source: §IV · p. 7

V. SIMULATING TIME-DEPENDENT HAMILTONIANS

This section establishes efficient simulation of sparse time-dependent Hamiltonians under differentiability and smoothness conditions. Under sufficient smoothness, its query complexity is comparable to the BACS method for time-independent evolution.

Section scope

  • Sparse time-dependent Hamiltonian evolution can be simulated efficiently when the Hamiltonian is at least piecewise twice-differentiable.The section also states that sufficiently smooth cases achieve query complexity comparable to the BACS algorithm for time-independent evolution.Source: §V · p. 7
  • The section presents explicit oracle descriptions and precise simulation-complexity results in terms of those oracles.These are introduced as the section’s steps toward the simulation result.Source: §V · p. 7

Complexity result

  • For sufficiently smooth Hamiltonians, the query complexity is comparable to the cost of BACS time-independent simulation.Source: §V · p. 7

A. Oracle Calls

The simulation uses oracles that expose locations and values of nonzero Hamiltonian matrix elements. The value oracle returns encoded matrix-element bits at discretized times, with values represented in polar form.

Oracle model

  • The oracle model supplies locations and values for nonzero matrix elements of each sparse Hamiltonian term.The paper allows a sum of terms that are sparse in different bases, with basis transformations supplied separately.Source: A. Oracle Calls · pp. 7–8
  • The column oracle returns a requested bit of a potentially nonzero column index in a specified row.Its inputs identify the bit, list entry, row, and Hamiltonian term.Source: A. Oracle Calls · p. 8
  • The matrix-value oracle returns a requested bit of a matrix element evaluated at a time on a finite mesh.The matrix elements are encoded in polar form as ρ(t) exp(iφ(t)).Source: A. Oracle Calls · p. 8

Quantum oracle interface

  • The quantum value oracle maps row and column registers plus an initially zero output register to the encoded matrix-element value.The displayed oracle takes p, µ, and q as classical inputs and x and y as quantum inputs.Source: A. Oracle Calls · p. 8

B. Constant Timestep Simulation Method

The constant-step method applies product-formula integrators to sparse, smooth Hamiltonians and bounds both integrator and discretization errors. It also treats finite discontinuities by omitting neighborhoods around them and simulating the remaining intervals.

Product-formula method

  • The method decomposes sparse Hamiltonian terms into one-sparse terms and applies Lie–Trotter–Suzuki product formulas to approximate evolution.The BACS decomposition is described as using 6d² one-sparse Hamiltonians for each d-sparse term.Source: B. Constant Timestep Simulation Method · pp. 8–9

Error accounting

  • The error analysis separates integrator error from round-off due to discretizing time and Hamiltonian matrix elements.The theorem’s precision conditions bound round-off by ǫ/2, and the integrator error is budgeted separately.Source: B. Constant Timestep Simulation Method · pp. 9–10

Constant-step theorem

  • The constant-step theorem bounds simulation error and oracle-query cost for d-sparse, Λ-2k-smooth Hamiltonian terms with stated oracle precision conditions.The theorem bounds calls to the Hamiltonian-value and column oracles, and separately constrains calls to basis-transformation oracles.Source: B. Constant Timestep Simulation Method · pp. 9–10

Discontinuities

  • For finitely many derivative singularities, the method omits neighborhoods around those points and simulates the remaining intervals.The supplied corollary imposes spacing and precision conditions on the intervals; the proof bounds the combined omission and integrator error by ǫ/2.Source: B. Constant Timestep Simulation Method · pp. 10–11

Conclusion

VI. ADAPTIVE DECOMPOSITION SCHEME

Adaptive time steps are chosen to make simulation cost depend on average Hamiltonian smoothness measures rather than their maxima. The construction bounds the integrator error while accounting for dependencies among the step sizes and their number.

VI. ADAPTIVE DECOMPOSITION SCHEME

  • The method chooses intervals so each integrator contributes at most ǫ/(2r) error, with interval size inversely proportional to the maximum Υ within that interval.Choosing the intervals is interdependent because the bound involves both the interval maximum and the unknown number r of steps.Source: §VI · pp. 11–12
  • The adaptive-step theorem assumes pointwise smoothness and a bound |∂tΥ(t)| ≤ K2[Υ(t)]2, and guarantees total error at most ǫ under the stated precision conditions.The step-count upper bound rg is used to resolve the dependence on the unknown number of intervals.Source: §VI · pp. 12, 14
  • The query-cost analysis bounds the number of exponentials using an upper bound on the step count and the number of one-sparse exponentials per kth-order approximation.The cost also depends on the one-sparse simulation cost C.Source: §VI · pp. 12, 14
  • Adaptive steps can reduce complexity when the average value of Υ is much smaller than its maximum, unlike constant steps whose cost depends on the maximum.This can help when the Hamiltonian has sharp peaks or discontinuities.Source: §VI · pp. 11, 14

VII. EXAMPLES

Two examples examine adaptive step sizing and adaptive integrator order. The results illustrate reduced exponential counts for a sharply peaked Hamiltonian and for a Hamiltonian with a singularity.

VII. EXAMPLES

  • In Fig. 1, adaptive stepping keeps Nexp approximately constant in a, whereas constant-step Nexp diverges as a approaches zero because max_{t∈[0,2]} Υ4(t) tends to infinity.The adaptive method’s integral of Υ4(t) over [0,2] depends only weakly on a; adaptive stepping can be advantageous when H(u) varies substantially over the simulation interval.Source: §VII · p. 15
  • For the non-analytic Hamiltonian, using k = 1 near the singularity and k = 2 farther away can reduce the number of exponentials compared with a single-order treatment.The second-order formula is unsuitable at t = 0 because the third derivative diverges; the interval split and its boundary t′ are varied to reduce exponential count.Source: §VII · p. 15

VIII. SIMULATING ONE-SPARSE HAMILTONIANS

The section gives a one-sparse Hamiltonian simulation procedure based on polar-form matrix-element encoding and controlled single-qubit rotations. It connects that implementation cost to the adaptive simulation results and states the resulting scaling and space use.

VIII. SIMULATING ONE-SPARSE HAMILTONIANS

  • A one-sparse exponential can be simulated using one qubit to store matrix elements and 3nH queries to QMatrixVal, under the lemma's smoothness assumptions.Polar decomposition enables rotations controlled by one qubit at a time.Source: §VIII · p. 15
  • The circuit implements the one-sparse evolution coherently by combining rotations for one- and two-dimensional subspaces, controlled by ancilla and row-membership information.The construction uses the BACS decomposition and restores its ancillas after the rotations.Source: §VIII · p. 17
  • For sufficiently smooth Hamiltonians, adaptive-step query complexity can scale close to linearly in the smoothness bound times the simulation time.The adaptive analogue of the constant-step result requires the theorem's conditions, including a bound on Υ′.Source: §VIII · p. 17
  • The simulation uses O(n(log*n)2) qubits, independent of ∥H∥ and ǫ.The bound follows from analysis of the BACS decomposition algorithm.Source: §VIII · p. 17

IX. CONCLUSIONS

The paper presents constant-step and adaptive-step algorithms for time-dependent Hamiltonian simulation, with adaptive stepping able to improve performance under suitable conditions. It also identifies limits on near-linear scaling and practical requirements for using the oracle-based schemes.

IX. CONCLUSIONS

  • The two algorithms use constant-size or adaptively chosen steps, and can have query complexity comparable to BACS when H(t) is a sum of sufficiently smooth terms.Adaptive stepping requires upper bounds on the Hamiltonian norm and its derivatives throughout the simulation.Source: §IX · p. 18
  • Near-linear scaling for the singularity-handling method requires H(t) to be a sum of piecewise sufficiently smooth terms.The authors also suggest lower-order formulas near singularities and higher-order formulas farther away.Source: §IX · p. 18
  • If quantities such as Λ are difficult to compute, the output may not meet error tolerance ǫ; n and the oracle's upper bound for ∥Hµ∥ must still be known.The authors suggest heuristic testing, such as a swap test between simulations using distinct uncertain-parameter values.Source: §IX · p. 18
  • Strictly linear-time simulation and query complexity poly-logarithmic in the reciprocal error tolerance remain open questions.The paper describes its own error dependence as sub-polynomial.Source: §IX · p. 18

Appendix A: Proof of Lemma 1

Appendix A proves Lemma 1 by bounding discretization errors in time and in the encoded Hamiltonian. The lemma's choices of n_H and n_t ensure the discretization error is at most ε/2.

Appendix A: Proof of Lemma 1

  • Lemma 1 gives choices of n_H and n_t that bound the discretization error by ε/2.The proof treats both time discretization and Hamiltonian representation error.Source: Appendix A · p. 18
  • The lemma applies to intervals of unequal duration and to sets I that are not continuous time intervals, provided the integrator is Lie-Trotter-Suzuki.The proof uses that integrator to obtain relation (A5) and determine its number of exponentials.Source: Appendix A · p. 19
  • The time-discretization error is bounded using Taylor's theorem and a choice of n_t satisfying condition (14).The displayed bounds are not included in these passages.Source: Appendix A · p. 19
  • With polar encoding, Hamiltonian discretization error includes modulus and phase inaccuracies and is bounded by ε_ρ + ε_φΛ_max.The same number of bits is chosen for modulus and phase; n_H is taken to exceed the value in (14).Source: Appendix A · p. 19

Appendix B: Bounds On Derivatives of Υ

Appendix B examines when the derivative condition used in adaptive simulation follows naturally from smoothness. The result depends on choosing the smoothness function appropriately, with a separate condition for finite-order smoothness.

Appendix B: Bounds On Derivatives of Υ

  • For the smallest Υ_P defined by P-pointwise smoothness, bounding its derivative uses Υ_P+1 because the order P+1 term is excluded from Υ_P's definition.The passage also states that a lower derivative bound follows in the same way.Source: Appendix B · p. 20
  • For finite P, if Υ_P+1(t) ≤ KΥ_P(t) throughout the interval, the derivative restriction in Theorem 2 follows.The stated restriction is |Υ′_P(t)| ≤ K²[Υ_P(t)]².Source: Appendix B · p. 20
  • When Υ_∞ is the smallest function giving ∞-pointwise smoothness, the additional finite-order restriction need not be imposed.The passage obtains this conclusion by taking the limit as P approaches infinity.Source: Appendix B · p. 20
  • For Υ-∞-pointwise-smooth Hamiltonian families, |Υ′(t)| ≤ [Υ(t)]² should hold when Υ is chosen appropriately, but a poor choice need not satisfy it.This motivates the adaptive method's derivative condition.Source: Appendix B · p. 20

Related papers

Loading 1011.3489v2…