  Quantum simulation of strongly correlated systems is potentially the most
feasible useful application of near-term quantum computers. Minimizing quantum
computational resources is crucial to achieving this goal. A promising class of
algorithms for this purpose consists of variational quantum eigensolvers
(VQEs). Among these, problem-tailored versions such as ADAPT-VQE that build
variational ans\"atze step by step from a predefined operator pool perform
particularly well in terms of circuit depths and variational parameter counts.
However, this improved performance comes at the expense of an additional
measurement overhead compared to standard VQEs. Here, we show that this
overhead can be reduced to an amount that grows only linearly with the number
$n$ of qubits, instead of quartically as in the original ADAPT-VQE. We do this
by proving that operator pools of size $2n-2$ can represent any state in
Hilbert space if chosen appropriately. We prove that this is the minimal size
of such "complete" pools, discuss their algebraic properties, and present
necessary and sufficient conditions for their completeness that allow us to
find such pools efficiently. We further show that, if the simulated problem
possesses symmetries, then complete pools can fail to yield convergent results,
unless the pool is chosen to obey certain symmetry rules. We demonstrate the
performance of such symmetry-adapted complete pools by using them in classical
simulations of ADAPT-VQE for several strongly correlated molecules. Our
findings are relevant for any VQE that uses an ansatz based on Pauli strings.
