  Quantum computing is a promising technology to address combinatorial
optimization problems, for example via the quantum approximate optimization
algorithm (QAOA). Its potential, however, hinges on scaling toy problems to
sizes relevant for industry. In this study, we address this challenge by an
elaborate combination of two decomposition methods, namely graph shrinking and
circuit cutting. Graph shrinking reduces the problem size before encoding into
QAOA circuits, while circuit cutting decomposes quantum circuits into fragments
for execution on medium-scale quantum computers. Our shrinking method
adaptively reduces the problem such that the resulting QAOA circuits are
particularly well-suited for circuit cutting. Moreover, we integrate two
cutting techniques which allows us to run the resulting circuit fragments
sequentially on the same device. We demonstrate the utility of our method by
successfully applying it to the archetypical traveling salesperson problem
(TSP) which often occurs as a sub-problem in practically relevant vehicle
routing applications. For a TSP with seven cities, we are able to retrieve an
optimum solution by consecutively running two 7-qubit QAOA circuits. Without
decomposition methods, we would require five times as many qubits. Our results
offer insights into the performance of algorithms for combinatorial
optimization problems within the constraints of current quantum technology.
