Quantum-inspired optimization for wavelength assignment
Aleksey S. Boev, Sergey R. Usmanov, Alexander M. Semenov, Maria M. Ushakova, Gleb V. Salahov, Alena S. Mastiukova, Evgeniy O. Kiktenko, Aleksey K. Fedorov
Problems related to wavelength assignment (WA) in optical communications networks involve allocating transmission wavelengths for known transmission paths between nodes that minimize a certain objective function, for example, the total number of wavelengths. Playing a central role in modern telecommunications, this problem belongs to NP-complete class for a general case so that obtaining optimal solutions for industry-relevant cases is exponentially hard. In this work, we propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. We propose an advanced embedding procedure to transform this problem into the quadratic unconstrained binary optimization (QUBO) form, having a improvement in the number of iterations with price-to-pay being a slight increase in the number of variables (“spins”). Then, we compare a quantum-inspired technique for solving the corresponding QUBO form against classical heuristic and industrial combinatorial solvers. The obtained numerical results indicate on an advantage of the quantum-inspired approach in a substantial number of test cases against the industrial combinatorial solver that works in the standard setting. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications and open a perspective for further analysis of the use of quantum computing devices.
Problems related to wavelength assignment (WA) in optical communications networks involve allocating transmission wavelengths for known transmission paths between nodes that minimize a certain objective function, for example, the total number of wavelengths. Playing a central role in modern telecommunications, this problem belongs to NP-complete class for a general case so that obtaining optimal solutions for industry-relevant cases is exponentially hard. In this work, we propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. We propose an advanced embedding procedure to transform this problem into the quadratic unconstrained binary optimization (QUBO) form, having a improvement in the number of iterations with price-to-pay being a slight increase in the number of variables (“spins”). Then, we compare a quantum-inspired technique for solving the corresponding QUBO form against classical heuristic and industrial combinatorial solvers. The obtained numerical results indicate on an advantage of the quantum-inspired approach in a substantial number of test cases against the industrial combinatorial solver that works in the standard setting. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications and open a perspective for further analysis of the use of quantum computing devices.
Routing and wavelength assignment with protection is an important problem in telecommunications. Given an optical network and incoming connection requests, a commonly studied variant of the problem aims to grant a maximum number of requests by assigning lightpaths with minimum network resource usage, while ensuring the provided services remain functional in the case of a single-link failure through dedicated protection paths. We consider a version where alternative lightpaths for requests are assumed to be given as a precomputed set and show that it is NP-hard. We formulate the problem as an Integer Programming (IP) model and also use it as a foundation to develop a Quadratic Unconstrained Binary Optimization (QUBO) model. We present necessary and sufficient conditions on objective function parameters to prioritize request granting objective over wavelength-link usage for both models, and a sufficient condition ensuring the exactness of the QUBO model. Moreover, we implement a problem-specific branch-and-cut algorithm for the IP model and employ a new quantum-inspired technology, Digital Annealer (DA), for the QUBO model. We conduct computational experiments on a large suite of nontrivial instances to assess the efficiency and efficacy of all of these approaches as well as two problem-specific heuristics. Although the objective penalty coefficient values that guarantee the exactness of the QUBO model were outside the acceptable range for DA, it always yielded feasible solutions even with smaller values in practice. The results show that the emerging technology DA outperforms the considered techniques coupled with GUROBI in finding mostly significantly better or as good solutions in two minutes compared to two-hour run time, whereas problem-specific heuristics fail to be competitive.
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.
We develop four different quadratic unconstrained binary optimization formulations of routing problems relevant to the optical transport layers in telecommunications networks. Our formulations handle joint routing and wavelength assignment, unicast, multicast trees, and shared risk avoidance. We show that this approach is viable, even for multicast, and we test and compare the effectiveness of each formulation at solving these problems using the DWave hybrid solver. We describe expedients we applied to ensure valid solutions, along with challenges of the QUBO approach.
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.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
The Quadratic Assignment Problem is a a classical constrained optimization problem used to model many real-life applications. We present experiments in solving the Quadratic Assignment Problem by means of Quantum Annealing and Quantum-inspired Annealing. We describe how to model this classical combinatorial problem in terms of QUBO (Quadratic Unconstrained Binary optimization) for implementing it on hardware solvers based on quantum or quantum-inspired annealing (D-Wave, Fujitsu Digital Annealing Unit and Fixstars Amplify Annealing Engine). We present performance result for these implementations and compare them with well established metaheuristic solvers on classical hardware, such as Robust Tabu Search and External Optimization.