SC21 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Towards Optimal Graph Coloring Using Rydberg Atoms

Authors: Giacomo Vitali, Paolo Viviani, Chiara Vercellino, Andrea Scarabosio, Alberto Scionti, and Olivier Terzo (Advanced Computing and Applications LINKS Foundation) and Edoardo Giusto and Bartolomeo Montrucchio (Polytechnic University of Turin)

Abstract: 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.

Best Poster Finalist (BP): no

Poster: PDF
Poster summary: PDF

Back to Poster Archive Listing