Dear quanta,
I mentioned this talk earlier - now it has a room: 6-310.
Here are some more details.
speaker: John Napp
title: Low-depth gradient measurements can improve convergence in
variational hybrid quantum-classical algorithms
abstract:
Variational algorithms, a broad class of quantum algorithms, have been
proposed in the context of quantum simulation, machine learning, and
combinatorial optimization as a way of potentially achieving a quantum
speedup on a near-term quantum device for a computational problem of
practical interest. Such algorithms use the quantum device only to prepare
parameterized quantum states and make simple measurements. A classical
"outer loop" 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, a few have proposed directly
measuring the gradient of the objective function. The measurement procedure
needed requires coherence time barely longer than needed to prepare a trial
state, and is much cheaper than procedures based on phase estimation. We
prove that strategies based on such gradient measurements can admit
substantially faster rates of convergence to the optimum in some contexts.
We first define a natural black-box setting for variational algorithms
which we prove our results with respect to. We define a simple but natural
class of problems for which a variational algorithm based on gradient
measurements and stochastic gradient descent converges to the optimum
quadratically faster in the precision than any possible strategy based on
estimating the objective function itself. We also present general upper
bounds for the cost of variational optimization for derivative-free,
stochastic gradient descent, and stochastic mirror descent methods in a
convex region.
-aram
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip