  Variational quantum algorithms, which have risen to prominence in the noisy
intermediate-scale quantum setting, require the implementation of a stochastic
optimizer on classical hardware. To date, most research has employed algorithms
based on the stochastic gradient iteration as the stochastic classical
optimizer. In this work we propose instead using stochastic optimization
algorithms that yield stochastic processes emulating the dynamics of classical
deterministic algorithms. This approach results in methods with theoretically
superior worst-case iteration complexities, at the expense of greater
per-iteration sample (shot) complexities. We investigate this trade-off both
theoretically and empirically and conclude that preferences for a choice of
stochastic optimizer should explicitly depend on a function of both latency and
shot execution times.
