Parameterized complexity

Stochastic gradient descent

Convergence (economics)

Context (archaeology)

Physics

Economic growth

Computer science

Mathematical optimization

Quantum algorithm

Gradient descent

Quantum mechanics

Mathematics

Biology

Hamiltonian (control theory)

Quantum error correction

Quantum circuit

Paleontology

Applied mathematics

Artificial neural network

Algorithm

Quantum machine learning

Artificial intelligence

Economics

Stochastic optimization

Quantum

Within the context of hybrid quantum-classical optimization, gradient descent based optimizers typically require the evaluation of expectation values with respect to the outcome of parameterized quantum circuits. In this work, we explore the consequences of the prior observation that estimation of these quantities on quantum hardware results in a form of stochastic gradient descent optimization. We formalize this notion, which allows us to show that in many relevant cases, including VQE, QAOA and certain quantum classifiers, estimating expectation values with $k$ measurement outcomes results in optimization algorithms whose convergence properties can be rigorously well understood, for any value of $k$. In fact, even using single measurement outcomes for the estimation of expectation values is sufficient. Moreover, in many settings the required gradients can be expressed as linear combinations of expectation values -- originating, e.g., from a sum over local terms of a Hamiltonian, a parameter shift rule, or a...

Stochastic gradient descent for hybrid quantum-classical optimization