  Variational quantum algorithms are a leading candidate for early applications
on noisy intermediate-scale quantum computers. These algorithms depend on a
classical optimization outer-loop that minimizes some function of a
parameterized quantum circuit. In practice, finite sampling error and gate
errors make this a stochastic optimization with unique challenges that must be
addressed at the level of the optimizer. The sharp trade-off between precision
and sampling time in conjunction with experimental constraints necessitates the
development of new optimization strategies to minimize overall wall clock time
in this setting. In this work, we introduce two optimization methods and
numerically compare their performance with common methods in use today. The
methods are surrogate model-based algorithms designed to improve reuse of
collected data. They do so by utilizing a least-squares quadratic fit of
sampled function values within a moving trusted region to estimate the gradient
or a policy gradient. To make fair comparisons between optimization methods, we
develop experimentally relevant cost models designed to balance efficiency in
testing and accuracy with respect to cloud quantum computing systems. The
results here underscore the need to both use relevant cost models and optimize
hyperparameters of existing optimization methods for competitive performance.
The methods introduced here have several practical advantages in realistic
experimental settings, and we have used one of them successfully in a
separately published experiment on Google's Sycamore device.
