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...
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2022-04-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2022-04-13-687/pdf/ |
| _version_ | 1818059056079699968 |
|---|---|
| author | Jordi R. Weggemans Alexander Urech Alexander Rausch Robert Spreeuw Richard Boucherie Florian Schreck Kareljan Schoutens Jiří Minář Florian Speelman |
| author_facet | Jordi R. Weggemans Alexander Urech Alexander Rausch Robert Spreeuw Richard Boucherie Florian Schreck Kareljan Schoutens Jiří Minář Florian Speelman |
| author_sort | Jordi R. Weggemans |
| collection | DOAJ |
| description | 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ő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 \geq 2$. Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm's performance. |
| first_indexed | 2024-12-10T13:10:27Z |
| format | Article |
| id | doaj.art-28157bd9be124219ac3610b6468c05c1 |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-12-10T13:10:27Z |
| publishDate | 2022-04-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-28157bd9be124219ac3610b6468c05c12022-12-22T01:47:40ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2022-04-01668710.22331/q-2022-04-13-68710.22331/q-2022-04-13-687Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approachJordi R. WeggemansAlexander UrechAlexander RauschRobert SpreeuwRichard BoucherieFlorian SchreckKareljan SchoutensJiří MinářFlorian SpeelmanWe 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ő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 \geq 2$. Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm's performance.https://quantum-journal.org/papers/q-2022-04-13-687/pdf/ |
| spellingShingle | Jordi R. Weggemans Alexander Urech Alexander Rausch Robert Spreeuw Richard Boucherie Florian Schreck Kareljan Schoutens Jiří Minář Florian Speelman Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach Quantum |
| title | Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach |
| title_full | Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach |
| title_fullStr | Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach |
| title_full_unstemmed | Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach |
| title_short | Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach |
| title_sort | solving correlation clustering with qaoa and a rydberg qudit system a full stack approach |
| url | https://quantum-journal.org/papers/q-2022-04-13-687/pdf/ |
| work_keys_str_mv | AT jordirweggemans solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach AT alexanderurech solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach AT alexanderrausch solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach AT robertspreeuw solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach AT richardboucherie solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach AT florianschreck solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach AT kareljanschoutens solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach AT jiriminar solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach AT florianspeelman solvingcorrelationclusteringwithqaoaandarydbergquditsystemafullstackapproach |