Riemannian gradient descent-based quantum algorithms for ground state preparation with guarantees

We investigate Riemannian gradient flows for preparing ground states of a desired Hamiltonian on a quantum device. We show that the number of steps of the corresponding Riemannian gradient descent (RGD) algorithm that prepares a ground state to a given precision depends on the structure of the Hamiltonian. Specifically, we develop an upper bound for the number of RGD steps that depends on the spectral gap of the Hamiltonian, the overlap between ground and initial state, and the target precision. In numerical experiments we study examples where we observe for a 1D Ising chain with nearest-neighbor interactions that the RGD steps needed to prepare a ground state scales linearly with the number of spins. For all-to-all couplings a quadratic scaling is obtained. To achieve efficient implementations while keeping convergence guarantees, we develop RGD approximations by randomly projecting the Riemannian gradient into polynomial-sized subspaces. We find that the speed of convergence of the randomly projected RGD critically depends on the size of the subspace the gradient is projected into. Finally, we develop efficient quantum device implementations based on Trotterization and a quantum stochastic drift-inspired protocol. We implement the resulting quantum algorithms on IBM's quantum devices and provide data for small-scale problems.