Analyzing performance of commercial quantum annealing solvers for the capacitated vehicle routing problem

Quantum Annealing (QA) is a heuristic search algorithm that can run on adiabatic quantum computation processors to solve combinatorial optimization problems. Although theoretical studies and simulations on classical hardware have shown encouraging results, these analyses often assume that the computation occurs in adiabatically closed systems without environmental interference. This is not a realistic assumption for real systems; therefore, without extensive empirical measurements on real quantum platforms, theory-based predictions, simulations on classical hardware, or limited tests do not accurately assess the current commercial capabilities. This study has assessed the quality of the solution provided by a commercial quantum annealing platform compared to known solutions for the capacitated vehicle routing problem. This study has conducted an extensive analysis on more than 30 hours of access to QA commercial platforms to investigate how the size of the problem and its complexity impact the accuracy of the solution and the time used to find a solution. Our results have found that the absolute error is between 0.12 and 0.55, and the time of the quantum processor unit is between 30 and 46 μs. Our results show that as the constraint density increases, the quality of the solution degrades. Therefore, more than the size of the problem, the complexity of the model plays a critical role, and practical applications should select formulations that minimize the constraint density.