Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians

摘要

We present a decomposition of the real time evolution operator $e^{-i T H}$of any local Hamiltonian $H$ on lattices $Lambda subseteq mathbb Z^D$ intolocal unitaries based on Lieb-Robinson bounds. Combining this with recentquantum simulation algorithms for real time evolution, we find that theresulting quantum simulation algorithm has gate count $mathcal O( T n~mathrm{polylog} (T n/epsilon))$ and depth $mathcal O( T~mathrm{polylog}(Tn/epsilon))$, where $n$ is the space volume or the numberof qubits, $T$ is the time of evolution, and $epsilon$ is the accuracy of thesimulation in operator norm. In contrast to this, the previous best quantumalgorithms have gate count $mathcal O(Tn^{2} ~mathrm{polylog} (Tn/epsilon))$. Our approach readily generalizes to time-dependent Hamiltoniansas well, and yields an algorithm with similar gate count for any piecewiseslowly varying time-dependent bounded local Hamiltonian. Finally, we also provea matching lower bound on the gate count of such a simulation, showing that anyquantum algorithm that can simulate a piecewise time-independent bounded localHamiltonian in one dimension requires $Omega(Tn / mathrm{polylog}(Tn) )$gates in the worst case. In the appendix, we prove a Lieb-Robinson boundtailored to Hamiltonians with small commutators between local terms. Unlikeprevious Lieb-Robinson bounds, our version gives zero Lieb-Robinson velocity inthe limit of commuting Hamiltonians. This improves the performance of ouralgorithm when the Hamiltonian is close to commuting.