Abstract

We introduce TE-PAI, which simulates time evolution exactly by sampling random quantum circuits for estimating the expectation value of observables. We prove that it simulates time evolution without discretisation or algorithmic error while achieving optimally shallow circuit depths that saturate the Lieb–Robinson bound. TE-PAI only requires executing very simple random circuits that consist of Pauli rotation gates of only two kinds of angles ±Δ and π, along with measurements. While TE-PAI is highly beneficial for NISQ devices, we additionally develop an optimised early fault-tolerant implementation, concluding that the approach requires orders of magnitude fewer T-states. Furthermore, TE-PAI allows for a highly configurable trade-off between circuit depth and measurement overhead by adjusting the angle Δ arbitrarily. This algorithm could serve as a major enabler for achieving practical quantum advantage in applications ranging from condensed matter physics to quantum chemistry.