  There has been much recent interest in near-term applications of quantum
computers, i.e., using quantum circuits that have short decoherence times due
to hardware limitations. Variational quantum algorithms (VQA), wherein an
optimization algorithm implemented on a classical computer evaluates a
parametrized quantum circuit as an objective function, are a leading framework
in this space. An enormous breadth of algorithms in this framework have been
proposed for solving a range of problems in machine learning, forecasting,
applied physics, and combinatorial optimization, among others.
  In this paper, we analyze the iteration complexity of VQA, that is, the
number of steps that VQA requires until its iterates satisfy a surrogate
measure of optimality. We argue that although VQA procedures incorporate
algorithms that can, in the idealized case, be modeled as classic procedures in
the optimization literature, the particular nature of noise in near-term
devices invalidates the claim of applicability of off-the-shelf analyses of
these algorithms. Specifically, noise makes the evaluations of the objective
function via quantum circuits biased. Commonly used optimization procedures,
such as SPSA and the parameter shift rule, can thus be seen as derivative-free
optimization algorithms with biased function evaluations, for which there are
currently no iteration complexity guarantees in the literature. We derive the
missing guarantees and find that the rate of convergence is unaffected.
However, the level of bias contributes unfavorably to both the constant
therein, and the asymptotic distance to stationarity, i.e., the more bias, the
farther one is guaranteed, at best, to reach a stationary point of the VQA
objective.
