  The promise of quantum computing to address complex problems requiring high
computational resources has long been hindered by the intrinsic and demanding
requirements of quantum hardware development. Nonetheless, the current state of
quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has
introduced algorithms and methods that are able to harness the computational
power of current quantum computers with advantages over classical computers
(referred to as quantum advantage). Achieving quantum advantage is of
particular relevance for the combinatorial optimization domain, since it often
implies solving an NP-Hard optimization problem. Moreover, combinatorial
problems are highly relevant for practical application areas, such as
operations research, or resource allocation problems. Among quantum computing
methods, Variational Quantum Algorithms (VQA) have emerged as one of the
strongest candidates towards reaching practical applicability of NISQ systems.
This paper explores the current state and recent developments of VQAs,
emphasizing their applicability to combinatorial optimization. We identify the
Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for
these problems. Furthermore, we implement QAOA circuits with varying depths to
solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the
potential and challenges of using VQAs in practical optimization tasks. We
release our code, dataset and optimized circuit parameters under
https://github.com/DanielFPerez/VQA-for-MaxCut.
