  Many optimization methods for training variational quantum algorithms are
based on estimating gradients of the cost function. Due to the statistical
nature of quantum measurements, this estimation requires many circuit
evaluations, which is a crucial bottleneck of the whole approach. We propose a
new gradient estimation method to mitigate this measurement challenge and
reduce the required measurement rounds. Within a Bayesian framework and based
on the generalized parameter shift rule, we use prior information about the
circuit to find an estimation strategy that minimizes expected statistical and
systematic errors simultaneously. We demonstrate that this approach can
significantly outperform traditional gradient estimation methods, reducing the
required measurement rounds by up to an order of magnitude for a common QAOA
setup. Our analysis also shows that an estimation via finite differences can
outperform the parameter shift rule in terms of gradient accuracy for small and
moderate measurement budgets.
