Benchmarking de algoritmos clássicos e variacionais quânticos para o problema MaxCut em redes de telecomunicações

Abstract

The maximum cut (MaxCut) problem is a Non-Deterministic Polynomial-time (NP)-hard problem with relevant applications in partitioning and resource allocation scenarios in telecommunications networks. In this work, a benchmarking among three approaches for its resolution ispresented: the exact solution by brute force, the classical approximation based on the GoemansWilliamson (GW) algorithm, the quantum variational approach through the Variational QuantumEigensolver (VQE), and the Quantum Approximate Optimization Algorithm (QAOA). To validate the feasibility of these methodologies in practical scenarios, this work incorporates a casestudy focused on the structural optimization of a telecommunications network where the algorithms were applied. The results demonstrate that the classical Goemans-Williamson algorithmoffers the best cost-benefit, maintaining high temporal efficiency and an AR close to 1,0000.Among the quantum models, a trade-off became evident: the VQE presented higher solutionquality at the expense of a parametric space of order O(N), while the QAOA achieved excellentparametric compression in the order of O(p), but with degradation in the cut quality as theproblem scaled. It is concluded that the main current barrier to quantum advantage in theseformulations does not lie in the mathematics of the ansätze, but in the exponential cost of theclassical simulation of state vectors, reinforcing the need for execution on real quantum hardwareto obtain practical gains