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

Computer Networks

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

Oumayma Bouchmal, Bruno Cimoli, Ripalta Stabile, Juan José Vegas Olmos, Idelfonso Tafur Monroy

Published May 13, 2025• 17 citations
Publisher

Abstract

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 ) ) .

DOI
10.1016/j.comnet.2025.111345

Related papers

Multiobjective Optimization and Network Routing With Near-Term Quantum Computers

Shao-Hen Chiew, Kilian Poirier, Rajesh Mishra +6 more

Multi-objective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multi-objective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multi-objective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multi-objective shortest path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA) – the go-to approach for tackling optimization problems on near-term quantum computers – we examine the Pareto plot that results from the scheme, and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA, and identify key challenges associated with this approach. Finally, through Amazon Braket we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.

arXiv:2308.08245•IEEE Transactions on Quantum Engineering•Jan 1, 2024•12 citations

Quantum Approximate Optimization Algorithm for Routing Optimization in 6G Optical Networks

Oumayma Bouchmal, Bruno Cimoli, Ripalta Stabile +2 more

Routing optimization refers to finding the most efficient path for data to travel between two devices on a network. In this paper, we propose the use of the Quantum Approximate Optimization Algorithm (QAOA) as a novel approach to routing optimization in the context of 6G networks. To this end, we first develop a cost function for single source single destination routing, which is then converted into a Quadratic Unconstrained Binary Optimization formulation. We subsequently extract the equivalent Variational Quantum Circuit of the QAOA from the optimization formulation. To test the performance of the QAOA, we utilize IBM's Qiskit toolkit and QASM-simulator and the Constrained by Linear Approximation optimizer to update the circuit parameters. Simulation results show that the proposed approach converges to the optimal solution, and only after less than 25 iteration, the QAOA was able to find the optimal path for the routing problem.

International Conference on Optical Network Design and Modeling (ONDM)•May 6, 2024•10 citations

Quantum computing approach for multi-objective routing and spectrum assignment optimization

Oumayma Bouchmal, Bruno Cimoli, Ripalta Stabile +5 more

Optimization problems are fundamental in a wide range of fields, including telecommunications, where efficient resource allocation is critical to ensure good network performance and high scalability. In the context of elastic optical networks (EONs), the multi-objective routing and spectrum assignment (MO-RSA) problem represents a key challenge, as it involves selecting a valid path and assigning frequency slots while fulfilling continuity and contiguity constraints and optimizing multiple conflicting objectives. This paper presents a novel, to the best of our knowledge, quantum-based approach to solving the MO-RSA problem. We first formulate the MO-RSA problem as a quadratic unconstrained binary optimization (QUBO) problem and then solve it using the quantum approximate optimization algorithm (QAOA). Our method accounts for both minimizing the total number of used links (or any non-negative additive metric) and maximizing the optical signal-to-noise ratio. For our simulations, we employed the Qiskit framework and IBM’s sampler-based quantum backend to implement and test the proposed approach. Our results demonstrate that by encoding the MO-RSA problem into a QUBO model and optimizing it with QAOA, we achieved an approximation ratio of 88% and a computational complexity of O ( n 2 ) , which represents a significant improvement over the exponential complexity of traditional integer linear programming methods.

Journal of Optical Communications and Networking•Mar 17, 2025•7 citations

Multi-Objective Routing Optimization Using Coherent Ising Machine in Wireless Multihop Networks

Yuxuan Lin, Chunxue Xu, Chuan Xi Wang

Multi-objective combinatorial optimization in wireless communication networks is a challenging task, particularly for large-scale and diverse topologies. Recent advances in quantum computing offer promising solutions for such problems. Coherent Ising Machines (CIM), a quantum-inspired algorithm, leverages quantum properties of coherent light, enabling faster convergence to the ground state. This paper applies CIM to multiobjective routing optimization in wireless multi-hop networks. We formulate the routing problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and map it onto an Ising model, allowing CIM to solve it. CIM demonstrates strong scalability across diverse network topologies without requiring topology-specific adjustments, overcoming the limitations of traditional quantum algorithms like Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE). Our results show that CIM provides feasible and near-optimal solutions for networks containing hundreds of nodes and thousands of edges. Additionally, a complexity analysis highlights CIM's increasing efficiency as network size grows.

arXiv:2503.07924•International Conference on Communications•Jun 8, 2025•5 citations

Quantum Approximate Multi-Objective Optimization in Routing Problems

Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo +3 more

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.

cs.ETCross-listedarXiv:2610.00168•Sep 17, 2026•0 citations

A UNIFIED BENCHMARKING FRAMEWORK FOR CLASSICAL AND QAOA-BASED MULTI-OBJECTIVE ROUTING IN COMMUNICATION NETWORKS

BALAMURUGAN N M KALAVATHI S

Multi-objective routing in communication networks requires simultaneous optimization of delay, congestion, and reliability—posing challenges for classical single-metric routing protocols. This paper presents a rigorous quantitative benchmarking framework comparing classical deterministic routing paradigms, namely Routing Information Protocol and Open Shortest Path First, against a quantum-assisted routing formulation based on the Quantum Approximate Optimization Algorithm (QAOA). The routing problem is encoded as a constrained Quadratic Unconstrained Binary Optimization (QUBO) model incorporating flow-conservation and path-continuity constraints. Random connected weighted graphs (10–20 nodes) were evaluated across 50 independent runs per topology size under a unified scalarized cost function (0.5D + 0.3C + 0.2L). Results demonstrate that deterministic link-state routing achieves optimal path selection with minimal computational complexity O(m log n), while QAOA attains near-optimal solutions (3–8% deviation) at significantly higher computational overhead due to qubit scaling and variational optimization loops. Scalability analysis reveals quadratic qubit growth with network size, limiting NISQ-era applicability. The study establishes a structured comparative benchmark and positions quantum routing as a complementary exploratory mechanism rather than a replacement for classical routing.

Journal of Theoretical and Applied Information Technology•Apr 15, 2026•0 citations
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 ) ) .
Multi-objective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multi-objective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multi-objective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multi-objective shortest path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA) – the go-to approach for tackling optimization problems on near-term quantum computers – we examine the Pareto plot that results from the scheme, and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA, and identify key challenges associated with this approach. Finally, through Amazon Braket we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.
Routing optimization refers to finding the most efficient path for data to travel between two devices on a network. In this paper, we propose the use of the Quantum Approximate Optimization Algorithm (QAOA) as a novel approach to routing optimization in the context of 6G networks. To this end, we first develop a cost function for single source single destination routing, which is then converted into a Quadratic Unconstrained Binary Optimization formulation. We subsequently extract the equivalent Variational Quantum Circuit of the QAOA from the optimization formulation. To test the performance of the QAOA, we utilize IBM's Qiskit toolkit and QASM-simulator and the Constrained by Linear Approximation optimizer to update the circuit parameters. Simulation results show that the proposed approach converges to the optimal solution, and only after less than 25 iteration, the QAOA was able to find the optimal path for the routing problem.
Optimization problems are fundamental in a wide range of fields, including telecommunications, where efficient resource allocation is critical to ensure good network performance and high scalability. In the context of elastic optical networks (EONs), the multi-objective routing and spectrum assignment (MO-RSA) problem represents a key challenge, as it involves selecting a valid path and assigning frequency slots while fulfilling continuity and contiguity constraints and optimizing multiple conflicting objectives. This paper presents a novel, to the best of our knowledge, quantum-based approach to solving the MO-RSA problem. We first formulate the MO-RSA problem as a quadratic unconstrained binary optimization (QUBO) problem and then solve it using the quantum approximate optimization algorithm (QAOA). Our method accounts for both minimizing the total number of used links (or any non-negative additive metric) and maximizing the optical signal-to-noise ratio. For our simulations, we employed the Qiskit framework and IBM’s sampler-based quantum backend to implement and test the proposed approach. Our results demonstrate that by encoding the MO-RSA problem into a QUBO model and optimizing it with QAOA, we achieved an approximation ratio of 88% and a computational complexity of O ( n 2 ) , which represents a significant improvement over the exponential complexity of traditional integer linear programming methods.
Multi-objective combinatorial optimization in wireless communication networks is a challenging task, particularly for large-scale and diverse topologies. Recent advances in quantum computing offer promising solutions for such problems. Coherent Ising Machines (CIM), a quantum-inspired algorithm, leverages quantum properties of coherent light, enabling faster convergence to the ground state. This paper applies CIM to multiobjective routing optimization in wireless multi-hop networks. We formulate the routing problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and map it onto an Ising model, allowing CIM to solve it. CIM demonstrates strong scalability across diverse network topologies without requiring topology-specific adjustments, overcoming the limitations of traditional quantum algorithms like Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE). Our results show that CIM provides feasible and near-optimal solutions for networks containing hundreds of nodes and thousands of edges. Additionally, a complexity analysis highlights CIM's increasing efficiency as network size grows.
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.
Multi-objective routing in communication networks requires simultaneous optimization of delay, congestion, and reliability—posing challenges for classical single-metric routing protocols. This paper presents a rigorous quantitative benchmarking framework comparing classical deterministic routing paradigms, namely Routing Information Protocol and Open Shortest Path First, against a quantum-assisted routing formulation based on the Quantum Approximate Optimization Algorithm (QAOA). The routing problem is encoded as a constrained Quadratic Unconstrained Binary Optimization (QUBO) model incorporating flow-conservation and path-continuity constraints. Random connected weighted graphs (10–20 nodes) were evaluated across 50 independent runs per topology size under a unified scalarized cost function (0.5D + 0.3C + 0.2L). Results demonstrate that deterministic link-state routing achieves optimal path selection with minimal computational complexity O(m log n), while QAOA attains near-optimal solutions (3–8% deviation) at significantly higher computational overhead due to qubit scaling and variational optimization loops. Scalability analysis reveals quadratic qubit growth with network size, limiting NISQ-era applicability. The study establishes a structured comparative benchmark and positions quantum routing as a complementary exploratory mechanism rather than a replacement for classical routing.