The Lie-Trotter formula, together with its higher-order generalizations, provides a direct approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly understood. We develop a theory of Trotter error that overcomes the limitations of prior approaches based on truncating the Baker-Campbell-Hausdorff expansion. Our analysis directly exploits the commutativity of operator summands, producing tighter error bounds for both real- and imaginary-time evolutions. Whereas previous work achieves similar goals for systems with geometric locality or Lie-algebraic structure, our approach holds, in general. We give a host of improved algorithms for digital quantum simulation and quantum Monte Carlo methods, including simulations of second-quantized plane-wave electronic structure, k-local Hamiltonians, rapidly decaying power-law interactions, clustered Hamiltonians, the transverse field Ising model, and quantum ferromagnets, nearly matching or even outperforming the best previous results. We obtain further speedups using the fact that product formulas can preserve the locality of the simulated system. Specifically, we show that local observables can be simulated with complexity independent of the system size for power-law interacting systems, which implies a Lieb-Robinson bound as a by-product. Our analysis reproduces known tight bounds for first- and second-order formulas. Our higher-order bound overestimates the complexity of simulating a one-dimensional Heisenberg model with an even-odd ordering of terms by only a factor of 5, and it is close to tight for power-law interactions and other orderings of terms. This result suggests that our theory can accurately characterize Trotter error in terms of both asymptotic scaling and constant prefactor.

}, issn = {2160-3308}, doi = {10.1103/PhysRevX.11.011020}, author = {Childs, Andrew M. and Su, Yuan and Tran, Minh C. and Wiebe, Nathan and Zhu, Shuchen} } @article {tran_destructive_2020, title = {Destructive {Error} {Interference} in {Product}-{Formula} {Lattice} {Simulation}, journal = {Phys. Rev. Lett.}, volume = {124}, number = {22}, year = {2020}, note = {Place: ONE PHYSICS ELLIPSE, COLLEGE PK, MD 20740-3844 USA Publisher: AMER PHYSICAL SOC Type: Article}, month = {jun}, abstract = {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.}, issn = {0031-9007}, doi = {10.1103/PhysRevLett.124.220502}, author = {Tran, Minh C. and Chu, Su-Kuan and Su, Yuan and Childs, Andrew M. and Gorshkov, V, Alexey} } @article { ISI:000548153300005, title = {Signaling and scrambling with strongly long-range interactions}, journal = {Phys. Rev. A}, volume = {102}, number = {1}, year = {2020}, month = {JUL 8}, pages = {010401}, publisher = {AMER PHYSICAL SOC}, type = {Article}, abstract = {Strongly long-range interacting quantum systems-those with interactions decaying as a power law 1/r(alpha) in the distance r on a D-dimensional lattice for alpha <= D-have received significant interest in recent years. They are present in leading experimental platforms for quantum computation and simulation, as well as in theoretical models of quantum-information scrambling and fast entanglement creation. Since no notion of locality is expected in such systems, a general understanding of their dynamics is lacking. In a step towards rectifying this problem, we prove two Lieb-Robinson-type bounds that constrain the time for signaling and scrambling in strongly long-range interacting systems, for which no tight bounds were previously known. Our first bound applies to systems mappable to free-particle Hamiltonians with long-range hopping, and is saturable for alpha <= D/2. Our second bound pertains to generic long-range interacting spin Hamiltonians and gives a tight lower bound for the signaling time to extensive subsets of the system for all alpha < D. This many-site signaling time lower bounds the scrambling time in strongly long-range interacting systems.}, issn = {1050-2947}, doi = {10.1103/PhysRevA.102.010401}, author = {Guo, Andrew Y. and Tran, Minh C. and Childs, Andrew M. and Gorshkov, V, Alexey and Gong, Zhe-Xuan} } @article {ISI:000474892400001, title = {Locality and Digital Quantum Simulation of Power-Law Interactions}, journal = {Phys. Rev. X}, volume = {9}, number = {3}, year = {2019}, month = {JUL 10}, pages = {031006}, publisher = {AMER PHYSICAL SOC}, type = {Article}, abstract = {The propagation of information in nonrelativistic 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{\textquoteright} 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).}, issn = {2160-3308}, doi = {10.1103/PhysRevX.9.031006}, author = {Tran, Minh C. and Guo, Andrew Y. and Su, Yuan and Garrison, James R. and Eldredge, Zachary and Foss-Feig, Michael and Childs, Andrew M. and Gorshkov, Alexey V.} }