Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters

By Dominic W. Berry, Andrew M. Childs, Robin Kothari. IEEE Annual Symposium on Foundations of Computer Science, 2015

524 citations recorded by the source corpus.

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 tau 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 sub linear dependence on tau.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/dfcad274ddb56705af120d7772f00d1fd97f8640

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 Computational Theory and Mathematics

Citations in the corpus

Generalized Quantum Signal Processing (2023, background): “ad, bd = S[0][d], S[1][d] θd = tan −1 ( |bd| |ad| )”
Hamiltonian Simulation by Qubitization (2016, methodology): “2A slightly tighter lower bound is Ω(q) queries, where q = min {q ∈ Z+ : < | sin(|τ |/q)|q = O((τ/q)q)} [6, 21].”
Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision (2017, background): “More recent work has streamlined these algorithms and improved their dependence on other parameters [6, 7, 15, 8, 14, 16].”
Toward the first quantum simulation with quantum speedup (2017, background): “Linear combination of quantum (23) O ( t log 3.”
Exponential improvement in precision for simulating sparse Hamiltonians (2013, methodology): “In more recent work, it has been shown that quantum walks can yield scaling close to linear in d, as well as polylogarithmic in , but only for the time-independent case [12].”
Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision (2015, methodology): “Corollary 10 also requires the unitary We now use the approach of Lemma 8 (speciﬁcally, in the form discussed immediately following the proof of the lemma) and the Hamiltonian simulation algorithm of [BCK15, Lemma 10] to implement U within precision ǫ ′ .”
Hamiltonian Simulation in the Interaction Picture (2018, background): “If we further assume that the computed matrix elements Hj,k are not exact, the number of bit of precision scales like np ∈ O (log (‖H‖t/ǫ)) [7].”
Quantum algorithms: an overview (2015, unknown): “Examples include work on increasing the accuracy of quantum simulation while retaining a fast runtime [14]; optimising the algorithm for particular applications such as quantum chemistry [48]; and exploring applications to new areas such as quantum (cid:12)eld theory [53].”
Optimal Hamiltonian Simulation by Quantum Signal Processing. (2016, methodology): “interesting physical system are described by the especially well-studied model of d-sparse Ĥ with at most d non-zero elements in every row, and the best known algorithms [18] are based on the Childs quantum walk [14], which builds upon the Szegedy walk [20], that simulates time evolution by arcsin (”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “While early works used phase estimation to invert the arcsin in the spectrum in order to recover the desired eigenvalues e−iEk , subsequent works achieved better scaling by using a linear combination of quantum walk steps [12].”
Variational Quantum Linear Solver (2019, methodology): “[9, 70].”