  Quantum processors promise a paradigm shift in high-performance computing
which needs to be assessed by accurate benchmarking measures. In this work, we
introduce a new benchmark for variational quantum algorithm (VQA), recently
proposed as a heuristic algorithm for small-scale quantum processors. In VQA, a
classical optimization algorithm guides the quantum dynamics of the processor
to yield the best solution for a given problem. A complete assessment of
scalability and competitiveness of VQA should take into account both the
quality and the time of dynamics optimization. The method of optimal stopping,
employed here, provides such an assessment by explicitly including time as a
cost factor. Here we showcase this measure for benchmarking VQA as a solver for
some quadratic unconstrained binary optimization. Moreover we show that a
better choice for the cost function of the classical routine can significantly
improve the performance of the VQA algorithm and even improving it's scaling
properties.
