Quantum Approximate Optimization Algorithm for Knapsack Resource Allocation Problems in Communication Systems
Junaid ur Rehman, Hayder Al-Hraishawi, Symeon Chatzinotas · 2023
Quantum technologies have recently scaled up from laboratories into commercial applications thanks to the rapid technical developments and the growing investments in quantum computing. These developments open up the way for the emergence of the so-called noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithms (QAOAs) represent a class of algorithms tailored for the NISQera computing for provisioning tangible quantum advantages. Meanwhile, wireless communications networks have become more complex over time and the pressure to conquer communications complexity is intense for both researchers and system designers. Specifically, a major optimization problem in this context is the resource allocation in modern communications where typically appears as an intricate 0/1 knapsack (0/1-KP) problem and finding its optimal solution using classical computers is prohibitively difficult. Thus, a parallel QAOA framework for optimizing the 0/1- KP problems is proposed in this paper. The proposal has the space complexity of$\mathcal{O} (n)$and pseudopolynomial time complexity of$\mathcal{O} (nW)$, where$W$is the knapsack's total capacity and$n$is the total number of items. However, the proposed QAOA solution is highly parallel and can be implemented on$M$NISQ devices of n-qubits each to obtain$\mathcal{O}(n W / M)$time complexity and$\mathcal{O} (nM)$space complexity. Numerical experiments show high approximation ratios even for shallow depth QAOA instances.