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. produces an unbiased estimator with finite average depth. This finite depth comes with an attenuation of the measured expectation value by a known amplitude, requiring more shots per circuit. The average gate count per circuit for simulation time t is \({\mathcal{O}}({t}^{2}{\mu }^{2})\) $\mathcal{O}\left(t^2{\mu }^2\right)$ with μ the sum of the Hamiltonian coefficients, without dependence on precision, providing a significant improvement over previous algorithms. With shot noise, the average runtime is \({\mathcal{O}}({t}^{2}{\mu }^{2}{\epsilon }^{-2})\) $\mathcal{O}\left(t^2{\mu }^2{ϵ}^{-2}\right)$ to reach precision ϵ. The only dependence in the sum of the coefficients makes it particularly adapted to non-sparse Hamiltonians. The algorithm generalizes to time-dependent Hamiltonians, appearing for example in adiabatic state preparation. These properties make it particularly suitable for present-day relatively noisy hardware that supports only circuits with moderate depth.