  Hybrid quantum-classical algorithms, such as variational quantum algorithms
(VQA), are suitable for implementation on NISQ computers. In this Letter we
expand an implicit step of VQAs: the classical pre-computation subroutine which
can non-trivially use classical algorithms to simplify, transform, or specify
problem instance-specific variational quantum circuits. In VQA there is a
trade-off between quality of solution and difficulty of circuit construction
and optimization. In one extreme, we find VQA for MAXCUT which are exact, but
circuit design or variational optimization is NP-HARD. At the other extreme are
low depth VQA, such as QAOA, with tractable circuit construction and
optimization but poor approximation ratios. Combining these two we define the
Spanning Tree QAOA (ST-QAOA) to solve MAXCUT, which uses an ansatz whose
structure is derived from an approximate classical solution and achieves the
same performance guarantee as the classical algorithm and hence can outperform
QAOA at low depth. In general, we propose integrating these classical
pre-computation subroutines into VQA to improve heuristic or guaranteed
performance.
