Exponential improvement in precision for simulating sparse Hamiltonians

By Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma. Forum of Mathematics, Sigma, 2013

451 citations recorded by the source corpus.

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 on n qubits can be simulated for time t with precision ε using O(τlog(τ/ε)/log log(τ/ε)) queries and O(τnlog2(τ/ε)/log log(τ/ε)) additional 2-qubit gates, where τ=d2||H||maxt. 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 significantly 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.

Subfields: Artificial Intelligence, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/9ee3dad0b5dfff68391ccf17e8ea9721629e6183

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

Citations in the corpus

Hamiltonian Simulation by Qubitization (2016, background): “See Cor. 7, 8, 9 for applications.”
Optimal Hamiltonian Simulation by Quantum Signal Processing. (2016, background): “sub-logarithmic scaling in error O ( τ log (τ/ ) log log (τ/ ) ) [17, 21].”
Toward the first quantum simulation with quantum speedup (2017, background): “Fractional-query simulation (22) O ( t log 2(t/ ) log log(t/ ) ) O ( n4 log n log log n )”
Q#: Enabling Scalable Quantum Computing and Development with a High-level DSL (2018, methodology): “Q# provides extensive built-in libraries containing implementations of these and other common subroutines, including the approximate quantum Fourier transform [4, 17], and a general version of oblivious amplitude amplification [1], making complex algorithm development simple and accessible.”
Low-Depth Quantum Simulation of Materials (2017, methodology): “[82] were first applied to chemistry in Refs.”
Hamiltonian Simulation in the Interaction Picture (2018, methodology): “Compared to prior art [6], this is a quadratic improvement in sparsity d.”
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters (2015, methodology): “…simulation, in terms of query complexity (i.e., the number of queries made to the oracles) and number of 2-qubit gates used, are one based on a Szegedy quantum walk [11, 13] and another based on simulating an unconventional model of query complexity called the fractional-query model [15].”
Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision (2017, methodology): “Subsequent work gave an algorithm with complexity poly(log(1/ ))—an exponential improvement—which is optimal in a black-box model [5].”
Generalized Quantum Signal Processing (2023, methodology): “One would then combine all parts together using linear combination of unitaries (LCU) [4], and furthermore perform a variant of amplitude amplification [17] on the resulting circuit.”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “Another easy-to-derive corollary of our machinery is robust oblivious amplitude amplification [11], which is a technique originally developed [10] for Hamiltonian simulation.”