Error-Mitigated Hamiltonian Simulation: Complexity Analysis and Optimization for Near-Term and Early-Fault-Tolerant Quantum Computers

Abstract

Simulating real-time dynamics under a Hamiltonian is a central goal of quantum information science. While numerous Hamiltonian-simulation quantum algorithms have been proposed, the effects of physical noise have rarely been incorporated into performance analysis, despite the non-negligible noise levels in quantum devices. We analyze noisy Hamiltonian simulation with quantum error mitigation (QEM) for Trotterized and randomized linear-combination-of-unitaries (LCU)-based Hamiltonian simulation algorithms. We give a complexity analysis of error-mitigated Hamiltonian simulation algorithms using the mean-squared error. Because quantum error mitigation incurs an exponential cost with the number of layers in quantum algorithms, there is a trade-off between the sampling cost and the bias in simulation accuracy or the algorithmic sampling overhead. Optimizing this trade-off, we derive an analytic depth-selection rule and characterize the optimal end-to-end scaling as a function of target accuracy and noise parameters. Importantly, optimizing the depth of randomized-LCU-based Hamiltonian simulation improves the simulation-time dependence of the sampling-overhead exponent from quadratic to linear. We further quantify the noise-characterization cost required for error mitigation via gate set tomography and the recently proposed space-time noise inversion method,showing that the latter can significantly reduce the characterization overhead.

13 pages, 1 figure