Lagrangian Relaxation Based Parallelized Quantum Annealing and Its Application in Network Function Virtualization

Abstract

Quantum computing is commonly considered one highly efficient computing method with the potential to revolutionize computation technology and solve problems that are currently unsolvable. However, due to the limitation of hardware equipment and an immature experimental base, quantum technology is still in its early stages and is far from achieving the expected performance, especially in solving large-scale complex problems. To break through these barriers, we propose a parallelized quantum annealing algorithm based on Lagrangian relaxation. The proposed algorithm divides the large-scale problem into several small problems and then employs multiple quantum computers to solve them. Our proposed approach overcomes the limited number of qubits and allows quantum computing to solve largescale optimization problems. Additionally, we incorporate a local search method to ensure this Lagrangian relaxation based quantum algorithm achieves an optimal solution. We use the proposed parallelized quantum annealing algorithm to solve optimal scheduling problems in network function virtualization networks. The problem is expressed in a linear optimization model that is NP-hard. Our proposed algorithm presents excellent time performance in solving this virtualized network functions scheduling problem, compared with the Lagrangian relaxation based classical algorithm.

Keywords

• Lagrangian relaxation
• quantum algorithm
• network function virtualization
• quantum computing
• virtualized network functions scheduling problem
• optimization problem