Locality and digital quantum simulation of power-law interactions. (arXiv:1808.05225v2 [quant-ph] UPDATED)

The propagation of information in non-relativistic quantum systems obeys a
speed limit known as a Lieb-Robinson bound. We derive a new Lieb-Robinson bound
for systems with interactions that decay with distance $r$ as a power law,
$1/r^\alpha$. The bound implies an effective light cone tighter than all
previous bounds. Our approach is based on a technique for approximating the
time evolution of a system, which was first introduced as part of a quantum
simulation algorithm by Haah et al., FOCS'18. To bound the error of the
approximation, we use a known Lieb-Robinson bound that is weaker than the bound
we establish. This result brings the analysis full circle, suggesting a deep
connection between Lieb-Robinson bounds and digital quantum simulation. In
addition to the new Lieb-Robinson bound, our analysis also gives an error bound
for the Haah et al. quantum simulation algorithm when used to simulate
power-law decaying interactions. In particular, we show that the gate count of
the algorithm scales with the system size better than existing algorithms when
$\alpha>3D$ (where $D$ is the number of dimensions).