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

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 Sr-87 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 ErdOs-Renyi 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.

Automated summary

In this study, we apply the quantum approximate optimization algorithm (QAOA) and qudits to solve the correlation clustering problem. We propose a full stack approach for correlation clustering using a neutral atom quantum computer, including the Hamiltonian formulation of the algorithm, performance analysis, and identification of suitable level structure. Our results show that the qudit implementation outperforms the qubit encoding. Numerical studies evaluate the algorithm's performance on complete and ErdOs-Renyi graphs, and indicate that QAOA consistently surpasses the Swamy bound for approximation ratio.