PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential improvement in precision for simulating sparse Hamiltonians

Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma

arXiv:1312.1414v2quant-ph

TL;DR

Sparse Hamiltonian simulation lacked an established ε-dependent lower bound and efficient discrete-query methods with sublogarithmic inverse-error dependence. The paper connects Hamiltonian dynamics with fractional- and continuous-query models, then improves their discrete-query simulation, obtaining an exponentially improved error dependence and matching ε-dependent lower bounds.

  • Problem

    Sparse Hamiltonian simulation and continuous-query conversion lacked efficient methods with sublogarithmic dependence on inverse error, and no ε-dependent lower bound was known for Hamiltonian simulation.

  • Method

    The paper reduces sparse Hamiltonian simulation to fractional- and continuous-query simulation and converts those models to discrete quantum queries using improved segmented constructions and oblivious amplitude amplification.

  • Results

    O(τ log(τ/ε)/loglog(τ/ε)) queries simulate a d-sparse Hamiltonian, and the algorithm has exponentially improved dependence on 1/ε over previous approaches.

  • Takeaways & Limitations

    The results establish that continuous and fractional query models are not much more powerful than the discrete model at very small error and make the error dependence optimal.

  • Takeaways & Limitations

    The continuous-query simulation algorithm is optimal in ε but suboptimal in T, and the tradeoff between T and ε remains unclear.

Abstract

from arXiv · show

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $ε$ using $O\big(τ\frac{\log(τ/ε)}{\log\log(τ/ε)}\big)$ queries and $O\big(τ\frac{\log^2(τ/ε)}{\log\log(τ/ε)}n\big)$ additional 2-qubit gates, where $τ= d^2 \|{H}\|_{\max} t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

1 Introduction

This paper develops sparse-Hamiltonian simulation algorithms with sublogarithmic dependence on inverse error, while also establishing matching error-dependent lower bounds. The approach connects Hamiltonian dynamics to fractional- and continuous-query simulation and efficiently converts those models to discrete queries.

  • Main result: The algorithm has no query dependence on n, improves dependence on d and t, and exponentially improves dependence on 1/ε over product-formula approaches.Its dependence on ε is better than the quantum-walk alternative, which has better dependence on ∥H∥maxt and d.
  • Time-dependent simulation: For time-dependent Hamiltonians, query complexity is unaffected by time dependence except through the largest max-norm, while gate complexity depends logarithmically on the derivative norm.The paper identifies this as a dramatic improvement over high-order product formulas, with another prior method trading worse dependence on t and ε for improved derivative dependence.
  • Structured Hamiltonians: For k-local Hamiltonians with M local terms, exploiting structure replaces τ with ˜τ = 2^kM∥H∥maxt.This improves the generic sparse-Hamiltonian parameter when additional locality structure is available.
  • Lower bounds: New lower bounds show that the algorithm’s dependence on ε is optimal, while its dependence on ∥H∥maxt is almost optimal.Theorem 1.2 gives an ε-dependent lower bound even for a 2-sparse Hamiltonian with ∥H∥max < 1 and constant simulation time.
  • Method: The algorithm relates sparse Hamiltonian simulation to fractional-query simulation and improves the conversion from continuous or fractional queries to discrete quantum queries.The conversion uses segments, controlled queries, and a new oblivious amplitude-amplification construction that does not require reflection about the input state.

2 High-level overview of techniques

The paper improves discrete simulation of continuous- and fractional-query algorithms, then reduces sparse Hamiltonian simulation to that framework and proves matching error lower bounds.

  • Continuous-query simulation: O(sublogarithmic inverse-error overhead) discrete queries simulate continuous- and fractional-query algorithms with bounded precision.The construction breaks algorithms into constant fractional-query pieces and uses the equivalence of continuous and fractional queries.
  • Continuous-query simulation: Oblivious amplitude amplification deterministically creates V|ψ⟩ without measurements, even when reflection about the input state is unavailable.This avoids the recursive fault-correction procedure used in the earlier strategy.
  • Sparse Hamiltonian simulation: Local edge coloring removes query-cost dependence on the number of qubits n in Hamiltonian simulation.The same trick can remove n-dependence from several known Hamiltonian simulation algorithms.
  • Sparse Hamiltonian simulation: The sparse-Hamiltonian algorithm reduces simulation to a generalized fractional-query problem, viewed through Lie-product-formula factors as fractional-query oracles.The reduction then invokes the improved discrete simulation of fractional queries.
  • Lower bounds: Lower bounds establish optimality in the error parameter by encoding parity computation into exact Hamiltonian simulation.The argument uses Hamiltonians whose repeated evolution produces nonzero amplitude on a parity-encoding state.

3 From continuous to discrete queries

This section establishes equivalence between continuous- and fractional-query models and develops a discrete-query simulation with improved error dependence. Its key simplification replaces fault correction with oblivious amplitude amplification, even without reflection about the input state.

  • Model equivalence: For any ε > 0, continuous- and fractional-query models are equivalent up to error ε, with fractional-query overhead depending on the average driving-Hamiltonian norm.The converse conversion preserves fractional-query complexity T with error at most ε.
  • Discrete simulation: A fractional-query algorithm of cost at most 1 can be implemented using O queries in the discrete-query model with error at most ε.The corresponding multiple-query result follows by concatenating constant-cost simulations.
  • Segment construction: Segments combine fractional-query gadgets and x-independent unitaries so that the desired operation is implemented with amplitude exactly 1/2.The exact amplitude enables one-step oblivious amplitude amplification.
  • Error dependence: The segment can be approximated with O queries whose dependence on ε is logarithmic divided by log log(1/ε), despite containing many controlled-query gates.The control-register Hamming weight determines how many queries are actually performed.
  • Amplitude amplification: Oblivious amplitude amplification avoids measuring control labels and the difficult fault-correction procedure used in earlier approaches.It uses a different reflection because the available reflection is not about the initial state.

4 Hamiltonian simulation

This section reduces sparse Hamiltonian simulation to fractional-query simulation by decomposing Hamiltonians into structured components. A simple bipartite edge coloring removes prior log* n overhead from the sparse decomposition.

  • Fractional-query reduction: The reduction applies the continuous-to-discrete query simulation to the resulting fractional-query algorithm, including multiple fractional-query oracles.The equivalence extends to unitaries with eigenvalues ±1, not only computational-basis diagonal queries.
  • Fractional-query reduction: The fractional-query framework implements sums of Hamiltonians whose components have two eigenvalues, after approximating the target evolution with a product formula.For components with eigenvalues 0 and π, the fractional-query cost scales with the evolution time and number of terms.
  • Sparse decomposition: A d-sparse Hamiltonian can be decomposed into d^2 1-sparse Hamiltonians, with each component query simulated using O(1) queries to the original Hamiltonian.This decomposition supports the reduction to structured query oracles.
  • Sparse decomposition: A simple coloring assigns each bipartite edge the ordered pair of its endpoint neighbor-list ranks, producing d^2 colors and 1-sparse color classes.The rank pair prevents two edges sharing a vertex from receiving the same color.
  • Time dependence: The same framework extends to time-dependent sparse Hamiltonians by partitioning the evolution into short intervals and controlling variation through the Hamiltonian derivative.The interval count is chosen so the accumulated approximation error is bounded by ε.
  • Structured Hamiltonians: For k-local Hamiltonians, an explicit 2^k-coloring exploits which local qubits are flipped, improving over the generic sparse coloring.A k-local term is 2^k-sparse, and the structure yields the improved coloring.

5 Time complexity

This section bounds the additional gate cost of the query-conversion and Hamiltonian-simulation algorithms. It uses compressed ancilla states and shows that time-dependent simulations depend logarithmically on the derivative norm.

  • Gate-cost optimization: The basic algorithm is inefficient because it relies on preparing an ancilla state with m = poly(h, T, 1/ε) components.A compressed version of this state avoids the direct preparation cost and does not require measuring control qubits.
  • Gate-cost optimization: Compressed ancilla encoding supports the required controlled operations and reflections without measuring the control qubits.The encoded state is truncated by Hamming weight and prepared using a circuit whose cost is analyzed in terms of k and m.
  • Continuous-query simulation: The continuous-query gate bound combines the per-evolution cost g with logarithmic terms in the average driving norm, T, and ε.The theorem assumes each intermediate time evolution is implementable with precision ε/T.
  • Gate-cost analysis: A constant-query segment can be implemented with gate cost O(k(g + log m)) plus encoded-ancilla preparation.Here g bounds the gates for implementing the relevant time evolutions between query operations.
  • Gate-cost analysis: Using O(T) segments with per-segment error ε/(5T) keeps the total error at most ε and yields the stated time complexity.The same segment analysis is applied to sparse Hamiltonian simulation with τ playing the role of T.
  • Time-dependent simulation: For time-dependent Hamiltonians, interval error is O(h′t^2/r^2), total error is O(h′t^2/r), and choosing r = Ω(h′t^2/ε) suffices.The derivative bound is h′ := max_s∈[0,t] ||dH(s)/ds||.

6 Lower bounds

The paper establishes lower bounds for sparse Hamiltonian simulation, including an error-dependent bound that matches the algorithm’s dependence on precision. The constructions encode parity in Hamiltonian dynamics, transferring query lower bounds to simulation.

  • Error-dependent bound: The weighted path Hamiltonian transfers the input parity into the endpoint reached from |0⟩, so measuring the endpoint yields an unbounded-error parity algorithm.Its endpoint transition amplitude is |sin(t/N)|^N, while the opposite-parity endpoint has zero amplitude.
  • Tightness: The parity construction shows that sufficiently accurate simulation requires Ω(N) queries, and the resulting lower bound makes the algorithm’s dependence on ǫ tight up to constant factors.The argument applies both to sparse Hamiltonian simulation and to continuous-query simulation through related constructions.
  • Continuous-query lower bound: A continuous-query lower bound also uses input-dependent gadgets and driving terms to form two paths whose connected component identifies parity.The gadget is assembled from conjugated query Hamiltonians and a driving Hamiltonian, then analyzed as disjoint paths.

7 Open questions

The paper leaves open several tradeoffs and parameter dependencies, especially the joint dependence on error, evolution time, and sparsity.

  • Error and evolution time: The continuous-query algorithm is optimal in ǫ alone but suboptimal in T, and the achievable ǫ–T tradeoff remains unclear.The paper notes that both a better algorithm and a stronger lower bound remain possible.
  • Time dependence: Combining the walk-based method’s linear dependence on t with this method’s stronger dependence on ǫ is identified as desirable.The walk-based approach has significantly worse dependence on ǫ despite its better time dependence.
  • Sparsity dependence: The sparsity dependence remains open because the method uses d^2+o(1) queries while a quantum-walk method uses O(d) queries.The paper asks whether a different Hamiltonian decomposition could improve the fractional-query approach.

A Proofs of known results

This appendix section states that it supplies proofs of claims already known or essentially implied by existing results.

  • Scope: The appendix provides completeness proofs for claims that are known or essentially follow from known results.No new theorem or quantitative result is stated in the supplied passage.

A.1 Equivalence of continuous- and fractional-query models

The paper establishes equivalence between continuous- and fractional-query models with the same query complexity, while converting between them through controlled approximations and accumulated error bounds.

  • Continuous to fractional: A continuous-query algorithm of complexity T can be implemented with fractional-query complexity T and m = O(ḩT^2/ǫ) fractional-query gates.Here ḩ is defined as the average norm of the driving Hamiltonian.
  • Fractional to continuous: Conversely, any fractional-query algorithm of complexity T can be implemented with continuous-query complexity T and error at most ǫ.The construction uses a piecewise-constant Hamiltonian over intervals of length T/m.
  • Error control: The continuous implementation approximates each fractional-query segment separately, then combines the segment errors using subadditivity for unitary implementations.Each exponential approximation contributes O(ǫ1), giving total error O(mǫ1).
  • Error control: Choosing ǫ1 = Θ(ǫ/m) makes the total simulation error at most ǫ.The required per-segment accuracy must also satisfy the stated bounds involving the fractional-query coefficients.

A.2 The Approximate Segment Lemma

The Approximate Segment Lemma converts a fractional-query implementation of a unitary into an approximate circuit using a query count independent of the original number of fractional queries. The construction truncates a control-state superposition and uses a nearby unitary to achieve error at most ε.

  • Gadget construction: Each fractional-query gadget succeeds with amplitude q_α and uses a control qubit whose |0⟩ state records successful application.The gadgets share a target register, and the m gadgets correspond to fractional queries Q_αi.
  • Segment construction: When all control qubits are |0^m⟩, the target is transformed to V|ψ⟩, with success amplitude determined by p = ∏_i q_αi.The construction adjusts this amplitude to 1/2 using an additional first qubit after showing p exceeds 1/4.
  • Approximate Segment Lemma: A fractional-query algorithm for V with total query complexity at most 1/5 can be implemented, within error ε, by a circuit using O(...) discrete queries.The Approximate Segment Lemma removes dependence on the potentially arbitrarily large number m of fractional queries.
  • Query reduction: At most k discrete queries are needed because each control string in the truncated superposition activates no more than k query gates.The controlled unitary is constructed by replacing inactive queries with identity operations.
  • Error analysis: The modified circuit is within error ε of the ideal unitary because a two-dimensional rotation maps the approximate prepared state to the ideal one while preserving the relevant first column.The resulting operator-distance bound is at most ε, and the lemma leaves the unitary's action unrestricted outside the designated input subspace.
Loading 1312.1414v2…