  Computing many-body ground state energies and resolving electronic structure
calculations are fundamental problems for fields such as quantum chemistry or
condensed matter. Several quantum computing algorithms that address these
problems exist, although it is often challenging to establish rigorous bounds
on their performances. Here we detail three algorithms that produce approximate
ground states for many-body and electronic structure problems, generalizing
some previously known results for 2-local Hamiltonians. Each method comes with
asymptotic bounds on the energies produced. The first one produces a separable
state which improves on random product states. We test it on a spinless Hubbard
model, validating numerically the theoretical result. The other two algorithms
produce entangled states via shallow or deep circuits, improving on the
energies of given initial states. We demonstrate their performance via
numerical experiments on a 2-dimensional Hubbard model, starting from a
checkerboard product state, as well as on some chemistry Hamiltonians, using
the Hartree-Fock state as reference. In both cases, we show that the
approximate energies produced are close to the exact ones. These algorithms
provide a way to systematically improve the estimation of ground state energies
and can be used stand-alone or in conjunction with existing quantum algorithms
for ground states.
