  Current universal quantum computers have a limited number of noisy qubits.
Because of this, it is difficult to use them to solve large-scale complex
optimization problems. In this paper we tackle this issue by proposing a
quantum optimization scheme where discrete classical variables are encoded in
non-orthogonal states of the quantum system. We develop the case of
non-orthogonal qubit states, with individual qubits on the quantum computer
handling more than one bit classical variable. Combining this idea with
Variational Quantum Eigensolvers (VQE) and quantum state tomography, we show
that it is possible to significantly reduce the number of qubits required by
quantum hardware to solve complex optimization problems. We benchmark our
algorithm by successfully optimizing a polynomial of degree 8 and 15 variables
using only 15 qubits. Our proposal opens the path towards solving real-life
useful optimization problems in today's limited quantum hardware.
