Improving Quantum and Classical Decomposition Methods for Vehicle Routing

Understand

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.