  Quantum optimization algorithms offer a promising route to finding the ground
states of target Hamiltonians on near-term quantum devices. None the less, it
remains necessary to limit the evolution time and circuit depth as much as
possible, since otherwise decoherence will degrade the computation. And even
where this is done, there always exists a non-negligible error in estimates of
the ground state energy. Here we present a scalable extrapolation approach to
mitigating this error, which significantly improves estimates obtained using
three of the most popular optimization algorithms: quantum annealing (QA), the
variational quantum eigensolver (VQE), and quantum imaginary time evolution
(QITE), at fixed evolution time or circuit depth. The approach is based on
extrapolating the annealing time to infinity, or the variance of estimates to
zero. The method is reasonably robust against noise, and for Hamiltonians which
only involve few-body interactions, the additional computational overhead is an
increase in the number of measurements by a constant factor. Analytic
derivations are provided for the quadratic convergence of estimates of energy
as a function of time in QA, and the linear convergence of estimates as a
function of variance in all three algorithms. We have verified the validity of
these approaches through both numerical simulation and experiments on an IBM
quantum computer. This work suggests a promising new way to enhance near-term
quantum computing through classical post-processing.
