  The Fermi-Hubbard model is of fundamental importance in condensed-matter
physics, yet is extremely challenging to solve numerically. Finding the ground
state of the Hubbard model using variational methods has been predicted to be
one of the first applications of near-term quantum computers. Here we carry out
a detailed analysis and optimisation of the complexity of variational quantum
algorithms for finding the ground state of the Hubbard model, including costs
associated with mapping to a real-world hardware platform. The depth
complexities we find are substantially lower than previous work. We performed
extensive numerical experiments for systems with up to 12 sites. The results
suggest that the variational ans\"atze we used -- an efficient variant of the
Hamiltonian Variational ansatz and a novel generalisation thereof -- will be
able to find the ground state of the Hubbard model with high fidelity in
relatively low quantum circuit depth. Our experiments include the effect of
realistic measurements and depolarising noise. If our numerical results on
small lattice sizes are representative of the somewhat larger lattices
accessible to near-term quantum hardware, they suggest that optimising over
quantum circuits with a gate depth less than a thousand could be sufficient to
solve instances of the Hubbard model beyond the capacity of classical exact
diagonalisation.
