Towards Optimal Graph Coloring Using Rydberg Atoms

Quantum mechanics is expected to revolutionize the computing landscape in the near future. Among the many candidate technologies for building universal quantum computers, Rydberg atoms-based systems stand out for being capable of performing both quantum simulations and working as gate-based universal quantum computers while operating at room temperature through an optical system. Moreover, they can potentially scale up to hundreds of quantum bits (qubits). In this work, we solve a Graph Coloring problem by iteratively computing the solutions of Maximal Independent Set (MIS) problems, exploiting the Rydberg blockade phenomenon. Experimental results using a simulation framework on the CINECA Marconi-100 supercomputer demonstrate the validity of the proposed approach.