  We propose and analyze a set of variational quantum algorithms for solving
quadratic unconstrained binary optimization problems where a problem consisting
of $n_c$ classical variables can be implemented on $\mathcal O(\log n_c)$
number of qubits. The underlying encoding scheme allows for a systematic
increase in correlations among the classical variables captured by a
variational quantum state by progressively increasing the number of qubits
involved. We first examine the simplest limit where all correlations are
neglected, i.e. when the quantum state can only describe statistically
independent classical variables. We apply this minimal encoding to find
approximate solutions of a general problem instance comprised of 64 classical
variables using 7 qubits. Next, we show how two-body correlations between the
classical variables can be incorporated in the variational quantum state and
how it can improve the quality of the approximate solutions. We give an example
by solving a 42-variable Max-Cut problem using only 8 qubits where we exploit
the specific topology of the problem. We analyze whether these cases can be
optimized efficiently given the limited resources available in state-of-the-art
quantum platforms. Lastly, we present the general framework for extending the
expressibility of the probability distribution to any multi-body correlations.
