Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.00168

Quantum Approximate Multi-Objective Optimization in Routing Problems

Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo, José Carlos Libois Neto, Fernando Augusto Caletti de Barros, Eduardo Inacio Duzzioni

cs.ETquant-phSubmitted Sep 15, 2026• Announced Sep 17, 2026• 0 citations
arXivHTMLPDF

Abstract

Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical ε-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.

Related papers

Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability

F. Picariello, G. Turati, R. Antonelli +10 more

The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.

quant-pharXiv:2512.10813•Dec 12, 2025•0 citations

QAOA for Efficient Urban Logistical Ecosystem

F. Picariello, Gloria Turati, R. Antonelli +10 more

The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization with widespread applications in logistics and transportation. As problem sizes increase, classical algorithms often fail to deliver high-quality solutions within practical time constraints. This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical algorithm, to address TSP instances under realistic conditions. We present a QUBO-based formulation of the TSP that integrates practical constraints reflecting real-world conditions—such as vehicle capacity, road accessibility, and time windows—while maintaining compatibility with limitations of current quantum hardware. Our analysis is conducted in a simulated environment, leveraging high-performance computing (HPC) resources to evaluate the algorithm’s performance across varying problem sizes and circuit depths. This approach enables a comprehensive assessment of QAOA’s capabilities and limitations in solving constrained TSP scenarios, thereby laying the groundwork for its deployment on future large-scale quantum hardware.

•Jan 1, 2025•0 citations

Reinforcement Learning based Quantum Approximate Optimization Algorithm for Vehicle Routing Problem.

Md. Aqib Aman, Fardin Azam Sakib

Reinforcement Learning–based Quantum Approximate Optimization Algorithm (QAOA-RL) is used to solve the Vehicle Routing Problem (VRP) by transforming it into a Quadratic Unconstrained Binary Optimization (QUBO) form. The RL agent learns to optimize QAOA parameters for better route selection. Results show that QAOA-RL achieves a lower total cost compared to exact ILP and heuristic Greedy Search methods. Although the training time is higher, the solution quality improves significantly for larger problem sizes. This study highlights QAOA-RL as a scalable and promising hybrid quantum–classical approach for real-world logistics optimization.

Transportation research procedia•Jan 1, 2026•0 citations

Enhancing vehicle routing problem through a qubit-efficient Symmetric Arc Reduction using Quantum Approximate Optimization Algorithm

Jayaraja A, Senthil Kumaran U

Introduction Finding the most efficient routes for a fleet of delivery vehicles remains a critical and costly challenge for nearly any logistics business. This core idea is known as the Vehicle Routing Problem (VRP). The primary goal is to minimize operational costs, such as the total travel distance or the number of trucks deployed, while ensuring all the customers are served. Because VRP is NP-hard, finding a perfect solution is often impossible, forcing industries to rely on classical approximate algorithms. However, quantum variational algorithms offer a new paradigm by iteratively optimizing parameters to navigate the solution space, presenting a new and promising avenue for finding better and faster solutions. Methods In this paper, we introduce Symmetric Arc Reduction in Quantum Approximate Optimization Algorithm (SAR-QAOA), which systematically eliminates redundant symmetric routing variables in the binary integer programming formulation prior to the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The proposed SAR-QAOA encodes edge-based VRP while reducing the qubit requirement from n ( n −1) to n ( n −1)/2, thereby improving the resource efficiency of the QUBO formulation by prioritizing regions of the solution space that are more likely to contain high-quality solutions; SAR enhances both search accuracy and computational efficiency. Results Experimental results on noiseless quantum simulators validate the feasibility of the proposed formulation and its integration with the QAOA framework, providing a promising foundation for future investigations on larger routing problems and evolving quantum hardware.

Frontiers in Artificial Intelligence•Oct 1, 2026•0 citations

Quantum Approximate Optimization Algorithm applied to multi-objective routing for large scale 6G networks

Oumayma Bouchmal, Bruno Cimoli, Ripalta Stabile +2 more

A multi-objective optimization problem involves optimizing two or more conflicting objectives simultaneously. This type of problem arises in many scientific and industrial areas and it is classified as NP-Hard. Network routing optimization with multiple objectives falls into this category. In the context of 6G networks, solving this problem will become even more challenging due to the exponential growth of Internet of Things devices and the high quality of service requirements. Finding good quality solutions for large-scale networks will be increasingly difficult. In this paper, we introduce a quantum-inspired routing optimization scheme in which noisy-intermediate scale quantum computers (NISQ) can be used to solve the Multi-Objective Routing Problem (MORP). We evaluate the application of the proposed scheme in detail by first developing the mathematical formulas for both single-objective and multi-objective routing and mapping the problem onto gate-based models by using the quadratic unconstrained binary optimization (QUBO) approach. To validate the proposed scheme, we use the quantum approximate optimization algorithm (QAOA), the go-to approach for solving combinatorial optimization problems that are classically intractable. For the simulation, we use the IBM-Qasm simulator and Qiskit framework. Additionally, we use the Chernoff Bound as a standard technique to estimate the sample complexity of QAOA. Finally, we provide a detailed numerical and theoretical analysis of the proposed scheme, including its time complexity, resource requirements, and the challenges associated with it. Our results demonstrate that the proposed approach operates with a time complexity of O ( E 2 ) per iteration in both single and multi-objective scenarios, with an overall runtime of ( n iteration + n CB ) ⋅ O ( E 2 ) influenced by the sampling overhead, significantly outperforming Dijkstra’s algorithm in the multi-objective case, where the complexity increases to O ( 2 k ( N ( k + log N ) + 2 k E ) ) .

Computer Networks•May 13, 2025•17 citations

Comparative Study of Variations in Quantum Approximate Optimization Algorithms for the Traveling Salesman Problem

Wenyang Qian, Robert Basili, Mary Mehrnoosh Eshaghian‐Wilner +3 more

The traveling salesman problem (TSP) is one of the most often-used NP-hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layer-wise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find that a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show that the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.

arXiv:2307.07243•Entropy•Aug 21, 2023•41 citations
Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical ε-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.
The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.
The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization with widespread applications in logistics and transportation. As problem sizes increase, classical algorithms often fail to deliver high-quality solutions within practical time constraints. This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical algorithm, to address TSP instances under realistic conditions. We present a QUBO-based formulation of the TSP that integrates practical constraints reflecting real-world conditions—such as vehicle capacity, road accessibility, and time windows—while maintaining compatibility with limitations of current quantum hardware. Our analysis is conducted in a simulated environment, leveraging high-performance computing (HPC) resources to evaluate the algorithm’s performance across varying problem sizes and circuit depths. This approach enables a comprehensive assessment of QAOA’s capabilities and limitations in solving constrained TSP scenarios, thereby laying the groundwork for its deployment on future large-scale quantum hardware.
Reinforcement Learning–based Quantum Approximate Optimization Algorithm (QAOA-RL) is used to solve the Vehicle Routing Problem (VRP) by transforming it into a Quadratic Unconstrained Binary Optimization (QUBO) form. The RL agent learns to optimize QAOA parameters for better route selection. Results show that QAOA-RL achieves a lower total cost compared to exact ILP and heuristic Greedy Search methods. Although the training time is higher, the solution quality improves significantly for larger problem sizes. This study highlights QAOA-RL as a scalable and promising hybrid quantum–classical approach for real-world logistics optimization.
Introduction Finding the most efficient routes for a fleet of delivery vehicles remains a critical and costly challenge for nearly any logistics business. This core idea is known as the Vehicle Routing Problem (VRP). The primary goal is to minimize operational costs, such as the total travel distance or the number of trucks deployed, while ensuring all the customers are served. Because VRP is NP-hard, finding a perfect solution is often impossible, forcing industries to rely on classical approximate algorithms. However, quantum variational algorithms offer a new paradigm by iteratively optimizing parameters to navigate the solution space, presenting a new and promising avenue for finding better and faster solutions. Methods In this paper, we introduce Symmetric Arc Reduction in Quantum Approximate Optimization Algorithm (SAR-QAOA), which systematically eliminates redundant symmetric routing variables in the binary integer programming formulation prior to the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The proposed SAR-QAOA encodes edge-based VRP while reducing the qubit requirement from n ( n −1) to n ( n −1)/2, thereby improving the resource efficiency of the QUBO formulation by prioritizing regions of the solution space that are more likely to contain high-quality solutions; SAR enhances both search accuracy and computational efficiency. Results Experimental results on noiseless quantum simulators validate the feasibility of the proposed formulation and its integration with the QAOA framework, providing a promising foundation for future investigations on larger routing problems and evolving quantum hardware.
A multi-objective optimization problem involves optimizing two or more conflicting objectives simultaneously. This type of problem arises in many scientific and industrial areas and it is classified as NP-Hard. Network routing optimization with multiple objectives falls into this category. In the context of 6G networks, solving this problem will become even more challenging due to the exponential growth of Internet of Things devices and the high quality of service requirements. Finding good quality solutions for large-scale networks will be increasingly difficult. In this paper, we introduce a quantum-inspired routing optimization scheme in which noisy-intermediate scale quantum computers (NISQ) can be used to solve the Multi-Objective Routing Problem (MORP). We evaluate the application of the proposed scheme in detail by first developing the mathematical formulas for both single-objective and multi-objective routing and mapping the problem onto gate-based models by using the quadratic unconstrained binary optimization (QUBO) approach. To validate the proposed scheme, we use the quantum approximate optimization algorithm (QAOA), the go-to approach for solving combinatorial optimization problems that are classically intractable. For the simulation, we use the IBM-Qasm simulator and Qiskit framework. Additionally, we use the Chernoff Bound as a standard technique to estimate the sample complexity of QAOA. Finally, we provide a detailed numerical and theoretical analysis of the proposed scheme, including its time complexity, resource requirements, and the challenges associated with it. Our results demonstrate that the proposed approach operates with a time complexity of O ( E 2 ) per iteration in both single and multi-objective scenarios, with an overall runtime of ( n iteration + n CB ) ⋅ O ( E 2 ) influenced by the sampling overhead, significantly outperforming Dijkstra’s algorithm in the multi-objective case, where the complexity increases to O ( 2 k ( N ( k + log N ) + 2 k E ) ) .
The traveling salesman problem (TSP) is one of the most often-used NP-hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layer-wise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find that a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show that the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.