Hamiltonian simulation with random inputs

The algorithmic error of digital quantum simulations is usually explored in terms of the spectral norm distance between the actual and ideal evolution operators. In practice, this worst-case error analysis may be unnecessarily pessimistic. To address this, we develop a theory of average-case performance of Hamiltonian simulation with random initial states. We relate the average-case error to the Frobenius norm of the multiplicative error and give upper bounds for the product formula (PF) and truncated Taylor series methods. As applications, we estimate average-case error for the digital Hamiltonian simulation of general lattice Hamiltonians and k-local Hamiltonians. In particular, for the nearest-neighbor Heisenberg chain with n spins, the error is quadratically reduced from O(n) in the worst case to O(sqrt[n]) on average for both the PF method and the Taylor series method. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models. We also apply our results to error analysis in the simulation of quantum scrambling.Ministry of Education (MOE)Published versionQ. Z. and A. F. S. acknowledge the support of the Department of Defense through the QuICS Hartree Postdoctoral Fellowship and Lanczos Graduate Fellowship, respectively. Q. Z. acknowledges the support from HKU Seed Fund for New Staff. Y. Z. acknowledges the support of NSFC No. 12205048, the Singapore MOE Tier 1 Grant No. RG162/19 and RG146/20, and FQXi-RFP-IPW-1903. T. L. was supported by the NSF Grant No. PHY-1818914 and a Samsung Advanced Institute of Technology Global Research Partnership. A. M. C. received support from the National Science Foundation (Grant No. CCF-1813814 and QLCI Grant No. OMA-2120757) and the Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams and Accelerated Research in Quantum Computing programs