Requirements for Early Quantum Utility and Quantum Utility in the Capacitated Vehicle Routing Problem
For researchers and practitioners in quantum optimization, this work provides a clear go/no-go metric for assessing when quantum devices might outperform classical heuristics on CVRP, though the conclusion is that advantage is unlikely without novel decomposition techniques.
The paper introduces a framework to determine when the Capacitated Vehicle Routing Problem (CVRP) can achieve early quantum advantage, finding that NISQ hardware is unlikely to provide advantage even with efficient encodings. For the Golden-5 benchmark, a HOBO encoding requires only 7,685 qubits, while QUBO encodings exceed 200,000 qubits.
We introduce a transparent, encoding-agnostic framework for determining when the Capacitated Vehicle Routing Problem (CVRP) can achieve early quantum advantage. Our analysis shows this is unlikely on noisy intermediate scale quantum (NISQ) hardware even in best case scenarios that use the most qubit-efficient direct encodings. Closed-form resource counts, combined with recent device benchmarks, yield three decisive go/no-go figures of merit: the quantum feasibility point and the qubit- and gate-feasibility lines, which place any CVRP instance on a single decision diagram. Contrasting a direct QUBO mapping with a space-efficient higher-order (HOBO) encoding reveals a large gap. Applied to early-advantage benchmarks such as Golden-5, our diagram shows that HOBO circuits require only 7,685 qubits, whereas comparable QUBO encodings still exceed 200,000 qubits. In addition to identifying candidate instances for early quantum advantage in CVRP, the framework provides a unifying go/no-go metric that ingests any CVRP encoding together with any hardware profile and highlights when quantum devices could challenge classical heuristics. Quantum advantage in CVRP would likely require innovative problem decomposition techniques.