  In the era of Noisy Intermediate-Scale Quantum (NISQ) computers it is crucial
to design quantum algorithms which do not require many qubits or deep circuits.
Unfortunately, the most well-known quantum algorithms are too demanding to be
run on currently available quantum devices. Moreover, even the state-of-the-art
algorithms developed for the NISQ era often suffer from high space complexity
requirements for particular problem classes. In this paper, we show that it is
possible to greatly reduce the number of qubits needed for the Traveling
Salesman Problem (TSP), a paradigmatic optimization task, at the cost of having
deeper variational circuits. While the focus is on this particular problem, we
claim that the approach can be generalized for other problems where the
standard bit-encoding is highly inefficient. Finally, we also propose encoding
schemes which smoothly interpolate between the qubit-efficient and the circuit
depth-efficient models. All the proposed encodings remain efficient to
implement within the Quantum Approximate Optimization Algorithm framework.
