Citation: Haah, Jeongwan, et al. "Quantum algorithm for simulating real time evolution of lattice Hamiltonians." SIAM Journal on Computing 52.6 (2021): FOCS18-250.
Web: https://arxiv.org/abs/1801.03922
Tags: Computer-scientific, Lieb-Robinson
This paper gives a lovely algorithm for simulating Hamiltonians using tensor networks, whose proof is based on Lieb-Robinson bounds. Not only is the proof based on Lieb-Robinson bounds, but the error incurred by the simulation is proportional to the Lieb-Robinson velocity. Hence, for Hamiltonians with small Lieb-Robinson velocities (like many toy models) this algorithm is quite efficient.
We now explain how the algorithm works for 1D Hamiltonian. First, you break up your Hamiltonian into intervals. Then, simulate time evolution along each of these intervals, then un-compute the Hamiltonian along the endpoints of the intervals. Then, compute the Hamilonian along regions which are the unions of the endpoints of the previous intervals. Doing this for a short time t approximately gives the same result as applying the Hamtilonian for that length t. The fact that this is true is based on the locality of the time evolution at small length scales, which comes from the Lieb-Robinson bound. Repeating this procedure over and over gives time evolution for macroscopic length scales t.
The algorithm sort of works like the Trotter formula in Lie theory, whereby one can break up the application of non-commuting operators into repeatedly applying those operators at small time scales. This Trotter-based numerical simulation algorithm was already known in the literature, as first described in
> Berry, Dominic W., et al. "Efficient quantum algorithms for simulating sparse Hamiltonians." Communications in Mathematical Physics 270 (2007): 359-371.