Exploring Quantum-Inspired and Classical Approaches for Solving the Graph Coloring Problem

The Graph Coloring Problem is a well-known NP-hard problem, where the goal is to assign colors to the vertices of a graph in such a way that no adjacent vertices share the same color, while minimizing the total number of colors used. Due to its computational complexity, large instances of this problem cannot be solved efficiently. In this thesis, we compare the state-of-the-art classical solvers, such as DSatur and Gurobi, to quantum-inspired solvers, targeting instances of increasing difficulty, such as Erdős-Rényi graphs. In our approach, the Graph Coloring problem is first converted into a Quadratic Unconstrained Binary Optimization (QUBO) problem, which can be efficiently tackled by tensor network techniques. Specifically, we recast the QUBO as a ground-state search for a corresponding spin glass Hamiltonian. The Quantum TEA suite is used to simulate the ground state of this Hamiltonian, employing tensor network ansatzes to represent quantum states efficiently. Our results demonstrate the effectiveness of quantum-inspired approaches and provide valuable insights into how quantum algorithms can scale and potentially outperform classical techniques in solving larger instances of the Graph Coloring Problem.