  We employ spectral analysis and compressed sensing to identify settings where
a variational algorithm's cost function can be recovered purely classically or
with minimal quantum computer access. We present theoretical and numerical
evidence supporting the viability of sparse recovery techniques. To demonstrate
this approach, we use basis pursuit denoising to efficiently recover simulated
Quantum Approximate Optimization Algorithm (QAOA) instances of large system
size from very few samples. Our results indicate that sparse recovery can
enable a more efficient use and distribution of quantum resources in the
optimisation of variational algorithms.
