  Computing the ground-state properties of quantum many-body systems is a
promising application of near-term quantum hardware with a potential impact in
many fields. The conventional algorithm quantum phase estimation uses deep
circuits and requires fault-tolerant technologies. Many quantum simulation
algorithms developed recently work in an inexact and variational manner to
exploit shallow circuits. In this work, we combine quantum Monte Carlo with
quantum computing and propose an algorithm for simulating the imaginary-time
evolution and solving the ground-state problem. By sampling the real-time
evolution operator with a random evolution time according to a modified
Cauchy-Lorentz distribution, we can compute the expected value of an observable
in imaginary-time evolution. Our algorithm approaches the exact solution given
a circuit depth increasing polylogarithmically with the desired accuracy.
Compared with quantum phase estimation, the Trotter step number, i.e. the
circuit depth, can be thousands of times smaller to achieve the same accuracy
in the ground-state energy. We verify the resilience to Trotterisation errors
caused by the finite circuit depth in the numerical simulation of various
models. The results show that Monte Carlo quantum simulation is promising even
without a fully fault-tolerant quantum computer.
