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.
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.
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 ) ) .
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 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.
Flexi-grid technology has revolutionized optical networking by enabling Elastic Optical Networks (EONs) that offer greater flexibility and dynamism compared to traditional fixed-grid systems. As data traffic continues to grow exponentially, the need for efficient and scalable solutions to the routing and spectrum assignment (RSA) problem in EONs becomes increasingly critical. The RSA problem, being NP-Hard, requires solutions that can simultaneously address both spatial routing and spectrum allocation. This paper proposes a novel quantum-based approach to solving the RSA problem. By formulating the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model, we employ the Quantum Approximate Optimization Algorithm (QAOA) to effectively solve it. Our approach is specifically designed to minimize end-to-end delay while satisfying the continuity and contiguity constraints of frequency slots. Simulations conducted using the Qiskit framework and IBM-QASM simulator validate the effectiveness of our method. We applied the QAOA-based RSA approach to small network topology, where the number of nodes and frequency slots was constrained by the limited qubit count on current quantum simulator. In this small network, the algorithm successfully converged to an optimal solution in less than 30 iterations, with a total runtime of approximately 10.7 s with an accuracy of 78.8%. Additionally, we conducted a comparative analysis between QAOA, integer linear programming, and deep reinforcement learning methods to evaluate the performance of the quantum-based approach relative to classical techniques. This work lays the foundation for future exploration of quantum computing in solving large-scale RSA problems in EONs, with the prospect of achieving quantum advantage as quantum technology continues to advance.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
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.