Dramatically reducing the number of measurements in ADAPT-VQE

ADAPT-VQE is a leading variational algorithm that circumvents the choice-of-ansatz conundrum by iteratively growing compact and arbitrarily accurate problem-tailored ansätze. However, the gradient-measurement step of the algorithm requires the estimation of O(N⁸) observables, which hinders the scaling of the algorithm to system sizes of practical interest. In this work we present an efficient strategy for measuring the pool gradients based on a partitioning of the relevant observables into mutually commuting sets. We argue that our approach is robust to shot-noise, and show that measuring the pool gradients is in fact only O(N) times as expensive as a naïve VQE iteration.