Convergence and efficiency proof of quantum imaginary time evolution for bounded order systems

Many current and near-future applications of quantum computing utilise parametric families of quantum circuits and variational methods that can suffer from obstacles including non-convergence to the global minimum due to local minima, critical slowing down, or exponential resource scaling. Here we show that quantum imaginary time evolution can overcome these obstacles if the underlying physical system satisfies a set of conditions. This includes many relevant applications such as ground state preparation for local theories in physics or chemistry, combinatorial optimisation problems, or quantum machine learning. In particular, we analyse the quantum imaginary time evolution showing convergence guarantees to the global minimum without critical slowing down and providing a priori estimates on the required evolution time which scale linearly in system size and inverse energy gap. Furthermore, a provided complexity analysis shows that quantum imaginary time evolution can be efficiently compiled into a parametric quantum circuit, finding the optimal parameters included, for a large class of physically relevant problems.