Study of Quantum Computing Applications in Graph Coloring Simulation and Optimization
Finding the minimum number of colors in which you can color a graph is a solution that requires combinatorial optimization, a challenge when it comes to a large number of vertices, in terms of runtime performance and convergence to an optimal solution. The problems that require great computational power form an excellent arena for testing the application of quantum algorithms. In particular, research on the development and simulation of the execution of quantum algorithms for graph staining can bring gains for solving some instances of this NP-hard problem. Research in quantum computing and mathematical modeling related to this problem has been growing in number and applications every year. New quantum algorithm models and simulators allow researchers to have more ways to deepen their studies and test their algorithms more closely to real problems. The implementation of hybrid algorithms, mathematical modeling in instances of quantum computers, such as Variational Quantum Eigensolver that combines classical optimizers with quantum measurements have proven to be efficient in problems that require a large number of iterations for convergence at an optimal value. These were explored and implemented to compare their performance in the coloring of graphs, which was the main theme of this qualification dissertation.