  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. Our numerical studies evaluate the algorithm's
performance by considering complete and Erd\H{o}s-R\'enyi 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 \geq 2$. Finally,
by analysing the effect of errors when solving complete graphs we find that
their inclusion severely limits the algorithm's performance.
