Destructive Error Interference in Product-Formula Lattice {Simulation

Quantum computers can efficiently simulate the dynamics of quantum systems. In this Letter, we study the cost of digitally simulating the dynamics of several physically relevant systems using the first-order product-formula algorithm. We show that the errors from different Trotterization steps in the algorithm can interfere destructively, yielding a much smaller error than previously estimated. In particular, we prove that the total error in simulating a nearest-neighbor interacting system of n sites for time t using the first-order product formula with r time slices is O(nt/r + nt(3)/r(2)) when nt(2)/r is less than a small constant. Given an error tolerance epsilon, the error bound yields an estimate of max\{O(n(2)t/epsilon), O(n(2)t(3/2)/epsilon(1/2))\} for the total gate count of the simulation. The estimate is tighter than previous bounds and matches the empirical performance observed in Childs et al. [Proc. Natl. Acad. Sci. U.S.A. 115, 9456 (2018)]. We also provide numerical evidence for potential improvements and conjecture an even tighter estimate for the gate count.