  Recent technological developments have focused the interest of the quantum
computing community on investigating how near-term devices could outperform
classical computers for practical applications. A central question that remains
open is whether their noise can be overcome or it fundamentally restricts any
potential quantum advantage. We present a transparent way of comparing
classical algorithms to quantum ones running on near-term quantum devices for a
large family of problems that include optimization problems and approximations
to the ground state energy of Hamiltonians. Our approach is based on the
combination of entropic inequalities that determine how fast the quantum
computation state converges to the fixed point of the noise model, together
with established classical methods of Gibbs state sampling. The approach is
extremely versatile and allows for its application to a large variety of
problems, noise models and quantum computing architectures. We use our result
to provide estimates for a variety of problems and architectures that have been
the focus of recent experiments, such as quantum annealers, variational quantum
eigensolvers, and quantum approximate optimization. The bounds we obtain
indicate that substantial quantum advantages are unlikely for classical
optimization unless the current noise rates are decreased by orders of
magnitude or the topology of the problem matches that of the device. This is
the case even if the number of qubits increases substantially. We reach similar
but less stringent conclusions for quantum Hamiltonian problems.
