Abstract
The paper presents a novel quantum method for addressing two fundamental routing problems: the Traveling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP), both central to routing challenges. The proposed method, named the Indirect Quantum Approximate Optimization Algorithm (IQAOA), leverages an indirect solution representation using ranking. Our contribution focuses on two main areas: 1) the indirect representation of solutions, and 2) the integration of this representation into an extended version of QAOA, called IQAOA. This approach offers an alternative to QAOA and includes the following components: 1) a quantum parameterized circuit designed to simulate string vectors on a quantum processor, 2) a classical meta-optimization method executed on a classical computer, and 3) the computation of the average cost for each string vector, achieved through a well-established algorithm from the operations research community tailored to the specific problem. IQAOA provides an efficient means to address quantum optimization problems by combining quantum and classical computation methods. Its primary advantage lies in deriving a quantum circuit that requires significantly fewer gates, making it suitable for execution on current noisy quantum computing platforms. Through numerical experiments employing IQAOA, we successfully solved instances of the 10-customer Traveling Salesman Problem (TSP) using the IBM simulator. To our knowledge, this is the largest application of a QAOA-based approach to solving the TSP. Additionally, IQAOA enables the resolution of the Vehicle Routing Problem (VRP) by leveraging the Split algorithm, which transforms a TSP permutation into a corresponding VRP solution.