  The impressive progress in quantum hardware in the last years has raised the
interest of the quantum computing community in harvesting the computational
power of such devices. However, in the absence of error correction, these
devices can only reliably implement very shallow circuits or comparatively
deeper circuits at the expense of a nontrivial density of errors. In this work,
we obtain extremely tight limitation bounds for standard NISQ proposals in both
the noisy and noiseless regimes, with or without error-mitigation tools. The
bounds limit the performance of both circuit model algorithms, such as QAOA,
and also continuous-time algorithms, such as quantum annealing. In the noisy
regime with local depolarizing noise $p$, we prove that at depths
$L=\mathcal{O}(p^{-1})$ it is exponentially unlikely that the outcome of a
noisy quantum circuit outperforms efficient classical algorithms for
combinatorial optimization problems like Max-Cut. Although previous results
already showed that classical algorithms outperform noisy quantum circuits at
constant depth, these results only held for the expectation value of the
output. Our results are based on newly developed quantum entropic and
concentration inequalities, which constitute a homogeneous toolkit of
theoretical methods from the quantum theory of optimal mass transport whose
potential usefulness goes beyond the study of variational quantum algorithms.
