Kothari: Exponential improvement in precision for simulating sparse Hamiltonians
Robin Kothari
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.
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