Graph coloring via quantum optimization on a Rydberg-qudit atom array

Tools

Angkhanawin, Toonyawat and Deger, Aydin and Pritchard, Jonathan D and Adams, C Stuart (2026) Graph coloring via quantum optimization on a Rydberg-qudit atom array. Quantum Science and Technology, 11 (2). 025012. ISSN 2058-9565 (https://doi.org/10.1088/2058-9565/ae3b6d)

[thumbnail of Angkhanawin-etal-QST-2026-Graph-coloring-via-quantum-optimization-on-a-Rydberg-qudit]
Preview
 Text. Filename: Angkhanawin-etal-QST-2026-Graph-coloring-via-quantum-optimization-on-a-Rydberg-qudit.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (1MB)| Preview

Abstract

Neutral atom arrays have emerged as a versatile candidate for the embedding of hard classical optimization problems. Prior work has focused on mapping problems onto finding the maximum independent set of weighted or unweighted unit disk graphs. In this paper we introduce a new approach to solving natively-embedded vertex graph coloring problems by performing coherent annealing with Rydberg-qudit atoms, where different same-parity Rydberg levels represent a distinct label or color. We demonstrate the ability to robustly find optimal graph colorings for chromatic numbers up to the number of distinct Rydberg states used, in our case k = 3. We analyze the impact of both the long-range potential tails and residual inter-state interactions, proposing encoding strategies that suppress errors in the resulting ground states. We discuss the experimental feasibility of this approach and propose extensions to solve higher chromatic number problems, providing a route towards direct solution of a wide range of real-world integer optimization problems using near-term neutral atom hardware.

ORCID iDs

Angkhanawin, Toonyawat, Deger, Aydin, Pritchard, Jonathan D ORCID logoORCID: https://orcid.org/0000-0003-2172-7340 and Adams, C Stuart;
CORE (COnnecting REpositories)