The second quantum revolution1 has been unfolding for over two decades, and numerous countries across the globe acknowledge the potential of these technologies. In the last decade, more than 15 publicly supported national initiatives were launched, with several of them having budgets exceeding billion euros, particularly in the UK,2 the US,3 the EU,4 France,5 Germany,6 India,7 and China.8 Both the number of new publications per year9 and the number of patents10 granted on quantum technologies (QT) have been climbing steadily for the last decade, along with the growing number of start-ups and renowned companies getting into the field. Recently, the field has been receiving attention from private funding sources, which some have been referring to as the ‘quantum gold rush.’11 Within two decades, QT has advanced from a topic that was mainly discussed in physics conferences to becoming a strong contender for a potential future industry.
In the Noisy Intermediate-Scale Quantum (NISQ) era of quantum computing, solving complex optimization problems such as the Vehicle Routing Problem (VRP) remains a formidable challenge. To overcome this obstacle, we introduce a novel method in this paper that focuses on reducing the number of edges in a graph based on Euclidean distances between vertices while preserving the crucial characteristics needed for solving the VRP. Our graph coarsening approach combined with the inflation method enables the reduced graph to be processed efficiently by classical, quantum or hybrid (quantum-classical) solvers, resulting in a faster computation time. When using the proposed method with hybrid algorithms, we have demonstrated an improvement of approximately 50% in the solution found by the hybrid solver. The practicality of our method on quantum hardware highlights its potential to contribute to the advancement of quantum and hybrid algorithms and applications during the NISQ era.