Accelerating vehicle routing problems on quantum computers

Vehicle routing problems (VRPs) are ubiquitous in transport and logistics optimization. Quantum approximate optimization algorithms are well-suited to these classically-hard combinatorial optimization problems, offering potential quantum advantage. However these algorithms should not be naively applied; the details of implementation are critical to the algorithm performance and can provide exponential enhancement. We discuss implementation decisions from the high-level initial problem formulation through to the low-level logic gate design. Judicious choices of the problem encoding, the QAOA classical optimization procedure, and the quantum unitary operators can greatly reduce the search space and enhance optimization performance. Further algorithmic enhancement on noise-susceptible quantum hardware can be achieved through lower-level control: we optimize and replace the quantum gates that constitute the quantum circuit. We present the impact of this end-to-end algorithm design on algorithm performance through simulation and hardware results.