Exploring the impact of graph locality for the resolution of the maximum- independent-set problem with neutral atom devices

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 44
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorDalyac, Constantinko
dc.contributor.authorHenry, Louis-Paulko
dc.contributor.authorKim, Minhyukko
dc.contributor.authorAhn, Jaewookko
dc.contributor.authorHenriet, Loïcko
dc.date.accessioned2023-12-26T05:00:09Z-
dc.date.available2023-12-26T05:00:09Z-
dc.date.created2023-12-26-
dc.date.issued2023-11-
dc.identifier.citationPhysical Review A, v.108, no.5-
dc.identifier.issn2469-9926-
dc.identifier.urihttp://hdl.handle.net/10203/316859-
dc.description.abstractIn the past years, many quantum algorithms have been proposed to tackle hard combinatorial problems. In particular, the maximum independent set (MIS) is a known NP-hard problem that can be naturally encoded in Rydberg atom arrays. By representing a graph with an ensemble of neutral atoms one can leverage Rydberg dynamics to naturally encode the constraints and the solution to MIS. However, the classes of graphs that can be directly mapped "vertex-to-atom"on standard devices with two-dimensional capabilities are currently limited to Unit-Disk graphs. In this setting, the inherent spatial locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an ϵ-approximate solution. In this work, we build upon recent progress made for using three-dimensioanl arrangements of atoms to embed more complex classes of graphs. We report experimental and theoretical results which represent important steps towards tackling combinatorial tasks on quantum computers for which no classical efficient ɛ-approximation scheme exists.-
dc.languageEnglish-
dc.publisherAmerican Physical Society-
dc.titleExploring the impact of graph locality for the resolution of the maximum- independent-set problem with neutral atom devices-
dc.typeArticle-
dc.identifier.scopusid2-s2.0-85178108660-
dc.type.rimsART-
dc.citation.volume108-
dc.citation.issue5-
dc.citation.publicationnamePhysical Review A-
dc.identifier.doi10.1103/physreva.108.052423-
dc.contributor.localauthorAhn, Jaewook-
dc.contributor.nonIdAuthorDalyac, Constantin-
dc.contributor.nonIdAuthorHenry, Louis-Paul-
dc.contributor.nonIdAuthorKim, Minhyuk-
dc.contributor.nonIdAuthorHenriet, Loïc-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
Appears in Collection
PH-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0