Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach

Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, Florian Speelman

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
8 Downloads (Pure)


We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits, which constitute a natural platform for such non-binary problems. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering, including Hamiltonian formulation of the algorithm, analysis of its performance, identification of a suitable level structure for 87Sr and specific gate design. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count. For single layer QAOA, we also prove (conjecture) a lower bound of 0.6367 (0.6699) for the approximation ratio on 3-regular graphs. Our numerical studies evaluate the algorithm’s performance by considering complete and Erdős-Rényi graphs of up to 7 vertices and clusters. We find that in all cases the QAOA surpasses the Swamy bound 0.7666 for the approximation ratio for QAOA depths p ≥ 2. Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm’s performance.

Original languageEnglish
Article number687
Pages (from-to)1-42
Number of pages42
Publication statusPublished - 13 Apr 2022


Dive into the research topics of 'Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach'. Together they form a unique fingerprint.

Cite this