Towards large-scale quantum optimization solvers with few qubits

Understand

We introduce a variational quantum solver for combinatorial optimizations over $m=\mathcal{O}(n^k)$ binary variables using only $n$ qubits, with tunable $k>1$.

• The number of parameters and circuit depth display mild linear and sublinear scalings in $m$, respectively.
• Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
• This leads to unprecedented quantum-solver performances.