  A broad class of hybrid quantum-classical algorithms known as "variational
algorithms" have been proposed in the context of quantum simulation, machine
learning, and combinatorial optimization as a means of potentially achieving a
quantum speedup on a near-term quantum device for a problem of practical
interest. Such algorithms use the quantum device only to prepare parameterized
quantum states and make simple measurements. A classical controller uses the
measurement results to perform an optimization of a classical function induced
by a quantum observable which defines the problem. While most prior works have
considered optimization strategies based on estimating the objective function
and doing a derivative-free or finite-difference-based optimization, some
recent proposals involve directly measuring observables corresponding to the
gradient of the objective function. The measurement procedure needed requires
coherence time barely longer than that needed to prepare a trial state. We
prove that strategies based on such gradient measurements can admit
substantially faster rates of convergence to the optimum in some contexts. We
first introduce a natural black-box setting for variational algorithms which we
prove our results with respect to. We define a simple class of problems for
which a variational algorithm based on low-depth gradient measurements and
stochastic gradient descent converges to the optimum substantially faster than
any possible strategy based on estimating the objective function itself, and
show that stochastic gradient descent is essentially optimal for this problem.
Importing known results from the stochastic optimization literature, we also
derive rigorous upper bounds on the cost of variational optimization in a
convex region when using gradient measurements in conjunction with certain
stochastic gradient descent or stochastic mirror descent algorithms.
