  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. For $m=7000$, numerical simulations produce
solutions competitive in quality with state-of-the-art classical solvers. In
turn, for $m=2000$, an experiment with $n=17$ trapped-ion qubits featured
MaxCut approximation ratios estimated to be beyond the hardness threshold
$0.941$. To our knowledge, this is the highest quality attained experimentally
on such sizes. Our findings offer a novel heuristics for quantum-inspired
solvers as well as a promising route towards solving commercially-relevant
problems on near term quantum devices.
