Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
Jordi R. Weggemans, Alexander Urech, Alexander Rausch, R. J. C. Spreeuw, Richard J. Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, Florian Speelman
Abstract
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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"/><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>87</mml:mn></mml:mrow></mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">S</mml:mi><mml:mi mathvariant="normal">r</mml:mi></mml:mrow></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>0.6367</mml:mn></mml:math> (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>0.6699</mml:mn></mml:math>) 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>0.7666</mml:mn></mml:math> for the approximation ratio for QAOA depths <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi><mml:mo>&#x2265;</mml:mo><mml:mn>2</mml:mn></mml:math>. Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm's performance.