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

Understand

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 ${}^{87}{\rm Sr}$ 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.