Hamiltonian dynamics on digital quantum computers without discretization error

We introduce an algorithm to compute expectation values of time-evolved observables on digital quantum computers that requires only bounded average circuit depth to reach arbitrary precision, i.e., it produces an unbiased estimator with finite average depth. This comes with a known attenuation factor that scales the measured expectation values and increases the number of shots, but the average gate count per circuit for simulation time t is O(t^2 μ^2), where μ is the sum of Hamiltonian coefficients, independent of precision. With shot noise, the average runtime is O(t^2 μ^2 ε^-2) to reach precision ε. The algorithm is particularly advantageous for non-sparse Hamiltonians and generalizes seamlessly to time-dependent Hamiltonians. These features make it suitable for near-term, noisy hardware with moderate circuit depth. We demonstrate performance on electronic structure (stretched H2O) and a 2D Ising model, outperforming Trotter and randomized compilation methods.