  Variational quantum circuits characterise the state of a quantum system
through the use of parameters that are optimised using classical optimisation
procedures that typically rely on gradient information. The circuit-execution
complexity of estimating the gradient of expectation values grows linearly with
the number of parameters in the circuit, thereby rendering such methods
prohibitively expensive. In this paper, we address this problem by proposing a
novel Quantum-Gradient Sampling algorithm that requires the execution of at
most two circuits per iteration to update the optimisable parameters, and with
a reduced number of shots. Furthermore, our proposed method achieves similar
asymptotic convergence rates to classical gradient descent, and empirically
outperforms gradient descent, randomised coordinate descent, and SPSA.
