  Variational quantum algorithms and, in particular, variants of the varational
quantum eigensolver have been proposed to address combinatorial optimization
(CO) problems. Using only shallow ansatz circuits, these approaches are deemed
suitable for current noisy intermediate-scale quantum hardware. However, the
resources required for training shallow variational quantum circuits often
scale superpolynomially in problem size. In this study we numerically
investigate what this scaling result means in practice for solving CO problems
using Max-Cut as a benchmark. For fixed resources, we compare the average
performance of training a shallow variational quantum circuit, sampling with
replacement, and a greedy algorithm starting from the same initial point as the
quantum algorithm. We identify a minimum problem size for which the quantum
algorithm can consistently outperform sampling and, for each problem size,
characterize the separation between the quantum algorithm and the greedy
algorithm. Furthermore, we extend the average case analysis by investigating
the correlation between the performance of the algorithms by instance. Our
results provide a step towards meaningful benchmarks of variational quantum
algorithms for CO problems for a realistic set of resources.
