Shot Frugal Optimization for Variational Quantum-Classical Hybrid Algorithms

Variational hybrid quantum-classical algorithms (VHQCAs) seem likely to be the first useful algorithms in the era of near-term quantum computing. There is however a justified concern that the number of measurements needed for these algorithms to converge might become prohibitive when scaling up to non-trivial problem sizes. We address this issue by adapting results from classical optimization to the problem of shot-frugal optimization of VHQCAs. Specifically, we present new techniques and compare them with standard methods to demonstrate the potential for improvement both with noiseless and noisy quantum devices.