Source-linked AI summary
Hamiltonian simulation with nearly optimal dependence on all parameters
Dominic W. Berry, Andrew M. Childs, Robin Kothari
TL;DR
Prior sparse Hamiltonian simulation methods achieve favorable scaling in either sparsity or error, but not both. The paper combines quantum walks with fractional-query simulation through Bessel-weighted linear combinations of walk steps, obtaining near-optimal scaling across the parameters and proving linear lower-bound dependence on τ. A remaining gap concerns the joint tradeoff between τ and ǫ.
Problem
Existing sparse Hamiltonian simulation methods trade good sparsity dependence against good error dependence, motivating a method that combines both advantages.
Method
The algorithm combines quantum-walk steps with fractional-query techniques, using a Bessel-weighted linear combination to approximate Hamiltonian evolution.
Results
The method has near-optimal scaling: slightly superlinear dependence on τ = d∥H∥maxt and sublogarithmic dependence on the allowed error, while any algorithm requires Ω(τ) queries.
Takeaways & Limitations
The combined approach provides the best features of quantum-walk and fractional-query simulation across the parameters of interest.
Takeaways & Limitations
A gap remains because the algorithm and lower bound impose different tradeoffs between τ and ǫ, leaving further improvement open.
Abstract
from arXiv · showhide
We present an algorithm for sparse Hamiltonian simulation whose complexity is optimal (up to log factors) as a function of all parameters of interest. Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity at the expense of poor scaling in the allowed error. In contrast, an approach based on fractional-query simulation provides optimal scaling in the error at the expense of poor scaling in the sparsity. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm's complexity (as measured by the number of queries and 2-qubit gates) is logarithmic in the inverse error, and nearly linear in the product $τ$ of the evolution time, the sparsity, and the magnitude of the largest entry of the Hamiltonian. Our dependence on the error is optimal, and we prove a new lower bound showing that no algorithm can have sublinear dependence on $τ$.
1 Introduction
Sparse Hamiltonian simulation is important because it captures physically realistic quantum dynamics, but prior methods trade sparsity efficiency against error dependence. This work combines quantum-walk and fractional-query techniques to obtain near-optimal parameter scaling and proves matching lower-bound structure.
- Problem: Sparse Hamiltonian simulation implements e^-iHt for a d-sparse Hamiltonian H over time t with precision ǫ.The task is defined in the diamond norm, using black-box access to the sparse Hamiltonian.
- Prior approaches: Prior quantum-walk methods scale linearly in sparsity and evolution time but have poor dependence on the allowed error, while fractional-query methods make the opposite tradeoff.The two approaches motivate a combined method with favorable scaling in both regimes.
- Results: Theorem 1 gives simulation complexity with τ := d∥H∥maxt, removing a factor of d from earlier query complexity and yielding near-linear rather than superquadratic dependence on d.The construction uses Bessel-function coefficients and achieves logarithmic dependence on τ/ǫ in the segment cost.
- Lower bound: A lower bound proves that every algorithm requires Ω(τ) queries, establishing that sublinear dependence on sparsity times evolution time is impossible.The proof strengthens separate Ω(d) and Ω(t) bounds by showing an Ω(dt) dependence.
- Open problem: The upper and lower bounds leave an open gap because the algorithm has a product tradeoff between τ and ǫ, whereas the lower bound has a sum.The paper also presents a parameter tradeoff family indexed by α.
- Method: The algorithm combines a Szegedy quantum walk with a linear combination of different numbers of walk steps, implemented using fractional-query techniques.The high-level construction approximates Hamiltonian evolution through a linear combination of powers of a walk unitary.
2 Overview of algorithms
The algorithm combines a Szegedy quantum walk with fractional-query techniques by applying a Bessel-weighted linear combination of walk steps. This corrects the walk’s phase approximation without distinguishing eigenspaces, while segmenting evolution and using oblivious amplitude amplification to control complexity.
- A superposition of quantum-walk steps effectively linearizes the arcsin function, correcting the phase applied during Hamiltonian simulation.The approach addresses phase deviation without increasing X or relying on phase estimation.
- The new operation acts identically on the two quantum-walk eigenspaces, eliminating the need to distinguish the µ+ and µ− sectors.This simultaneously handles both sectors and corrects the applied phase.
- The Bessel-function coefficients make the truncated linear combination accurate with a cutoff k logarithmic in 1/ǫ.Bessel functions decay exponentially for large step numbers, so truncation achieves error at most ǫ with logarithmic error dependence.
- LCU techniques implement the Bessel-weighted walk-step combination, while oblivious amplitude amplification makes each segment deterministic.The algorithm divides the evolution into shorter segments and applies the amplified operation to each segment.
- Choosing z = O(1) yields O(τ) segments, giving near-linear dependence on the evolution time, sparsity, and maximum-entry product τ.Alternatively, z = −τ^α gives k = O(τ^α + log(1/ǫ)), O(τ^(1−α)) segments, and O(τ^(α/2)) amplification steps.
3 Analysis of algorithms
The analysis combines quantum-walk steps through linear combinations and robust oblivious amplitude amplification to implement accurate Hamiltonian evolution. It derives query and gate complexities for the main algorithm and a τ–ǫ tradeoff, while establishing approximation error and lower-level implementation costs.
- Quantum walk: The quantum walk is constructed by duplicating the Hilbert space, preparing controlled states, applying walk steps, and reversing the preparation.The walk uses a swap-based unitary and returns the output to the original space with the ancilla restored to |0⟩.
- Linear combination of unitaries: Linear combinations of unitaries are implemented using ancilla preparation, controlled selection, inverse preparation, and oblivious amplitude amplification.The LCU construction first produces the desired combination with postselection and then makes the operation deterministic through robust amplification.
- Main algorithm: The main phase-correction problem arises because arcsin ν is nonlinear, so the algorithm superposes different numbers of walk steps.This superposition addresses both quantum-walk eigenphase sectors while correcting the applied phase.
- Approximation and amplification: The exact target operation is V∞, while finite truncations approximate it with error controlled by the chosen coefficient cutoff.Robust amplification contributes O(δ) error and uses O(a) controlled-selection operations with O(Ma) additional 2-qubit gates.
- Complexity analysis: O(τk) complexity follows from O(tXd) segments, O(k) walk operations per segment, and choosing X = ∥H∥max.The resulting query complexity is converted to gate complexity by multiplying by the cost of implementing the quantum walk, yielding an additional O(n + F(log(∥H∥t/ǫ))) factor.
4 Lower bound
The section proves lower bounds showing that sparse Hamiltonian simulation requires linear dependence on τ, with stronger combined bounds for intermediate error regimes.
- The main lower bound: The lower bound is Ω(td), rather than merely Ω(d + t), because evolution time and sparsity can vary independently.The proof adapts a parity-based argument so that the product dependence is captured directly.
- The main lower bound: Ω(td) queries are required for some 2d-sparse Hamiltonians with constant precision and ∥H∥max = Θ(1).The construction uses Hamiltonian evolution to compute the parity of an N-bit string, establishing the bound through quantum query complexity.
- The construction: The constructed Hamiltonian duplicates each path vertex d times, producing maximum degree 2d while maintaining ∥H∥max = Θ(1).Evolution from the initial uniform-register state reaches a basis state encoding the parity of the input string.
- The construction: For t = Nπ/2d, evolution maps |0, 0, ∗⟩ to |N, x1 ⊕· · ·⊕xN, ∗⟩, thereby revealing the parity of x.Since parity requires Ω(N) quantum queries, the simulation requires Ω(N) = Ω(td) queries.
5 Conclusion
The conclusion combines quantum-walk and fractional-query ideas to obtain near-optimal scaling across the parameters of sparse Hamiltonian simulation. It also identifies an unresolved tradeoff gap and a possible application to operation conversion.
- Conclusion: The technique combines quantum walks and fractional-query simulation, improving performance over both previous approaches.The algorithm achieves near-optimal scaling with respect to all parameters of interest.
- Conclusion: The query complexity is only slightly superlinear in τ, while linear dependence on τ is proven optimal.The method is also sublogarithmic in the allowed error, which is stated to be optimal.
- Conclusion: A gap remains between the algorithm’s complexity and the lower bound because they impose different tradeoffs between τ and ǫ.Whether performance can be further improved remains open, although strictly matching the lower-bound scaling is ruled out.
- Conclusion: The technique can potentially support operation conversion by using a superposition of operations instead of phase estimation.In this work, a quantum-walk step is converted into Hamiltonian evolution.
A Proofs of technical lemmas
The technical appendix develops operator-norm bounds and controls Bessel-function coefficients used in the simulation analysis. These estimates support approximation and error bounds for the constructed operations.
- Operator bounds: The proofs compare two operators on pure states using a basis representation and their eigenvalues to bound trace-norm and spectral-norm differences.The argument uses inequalities relating overlaps, spectral norms, and trace norms.
- Operator bounds: Trace-norm estimates are extended to channels through positivity and invariance under tensoring with the identity.For non-negative Hermitian operators, the trace norm equals the trace, enabling the remaining-part bound.
- Bessel coefficients: The Bessel-function analysis shows that normalized coefficients am closely approximate Jm(z) for relevant indices.The proof uses bounds on Jm(z), the relation J−m(z) = (−1)^mJm(z), and a condition |z| ≤ k.
- Bessel coefficients: Cauchy–Schwarz bounds the Bessel-coefficient tail, and choosing k = ⌈ez/2⌉ makes the second contribution O(1).This yields the stated asymptotic bound for S(z).