Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

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

Constantin Dalyac, Louis-Paul Henry, Minhyuk Kim, Jaewook Ahn, Loïc Henriet

Published Nov 21, 2023• 15 citations
Publisher

Abstract

In 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 $\ensuremath{\epsilon}$-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 $\ensuremath{\varepsilon}$-approximation scheme exists.

DOI
10.1103/physreva.108.052423

Related papers

Exploring the impact of graph locality for the resolution of MIS with neutral atom devices

Constantin Dalyac, Louis-Paul Henry, Minhyuk Kim +2 more

In 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 2D 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 3D 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 $\varepsilon$-approximation scheme exists.

arXiv:2306.13373•Jun 23, 2023•1 citation

Embedding the MIS problem for non-local graphs with bounded degree using 3D arrays of atoms

Constantin Dalyac, Loïc Henriet

In the past years, many quantum algorithms have been proposed to tackle hard combinatorial problems. These algorithms, which have been studied in depth in complexity theory, are at the heart of many industrial applications. 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 node-to-atom on such devices are limited to Unit-Disk graphs. In this setting, the inherent locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an ε-approximate solution. In this work, we present a deterministic and polynomial-time construction to embed a large family of non-local graphs in 3D atomic arrays. This construction is a first crucial step towards tackling combinatorial tasks on quantum computers for which no classical efficient ε-approximation scheme exists.

arXiv:2209.05164•Sep 12, 2022•0 citations

Local Rydberg blockade regimes for disk graph embedding and quantum optimization

Elie Bermot, Lucia C. Valor, Wesley da Silva Coelho +2 more

Rydberg atom arrays are a powerful platform for solving combinatorial optimization problems, owing to the Rydberg blockade mechanism, which imposes effective constraints on simultaneous atomic excitations. These constraints have enabled the encoding of the Maximum Independent Set (MIS) problem on unit disk graphs, where atoms interact within a fixed, globally defined blockade radius. However, this restriction limits the class of addressable problems. A natural extension is to consider disk graphs, which generalize unit disk graphs by allowing arbitrary disk radii and correspond to the intersection graphs of disks in the plane. Embedding such graphs in Rydberg systems requires moving beyond the standard, globally uniform blockade model. In this work, we introduce a local Rydberg blockade regime, which emerges when local drives are applied to different pairs of atoms involved in a potential interaction. We develop a general theoretical framework for this regime and propose two novel metrics, the correlation matrix and the maximum independence violation, to quantify the quality of the embedding. Using these metrics, we demonstrate that disk graphs can be meaningfully embedded into Rydberg atom arrays under local drive schemes, thereby expanding the landscape of quantum-addressable optimization problems. Finally, when evaluating approximate solutions of the MIS problem, characterized by near-optimal independent sets, local drive approaches exhibit significantly improved performance over global ones. These results highlight the practical advantage of local blockade engineering for approximate combinatorial optimization and open a path toward leveraging the analog capabilities of Rydberg platforms beyond conventional geometric constraints.

arXiv:2506.13228•Jun 16, 2025•0 citations

Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors

Pierre Cazals, François, Aymeric, Loïc Henriet +9 more

The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.

arXiv:2502.04291•Feb 6, 2025•0 citations

Approximate combinatorial optimization with Rydberg atoms: The barrier of interpretability

Christian de Correc, Thomas Ayral, Corentin Bertrand

Analog quantum computing with Rydberg atoms is seen as an avenue to solve hard graph optimization problems, because they naturally encode the maximum independent set (MIS) problem on unit disk (UD) graphs, a problem that admits rather efficient approximation schemes on classical computers. Going beyond UD-MIS to address generic graphs requires embedding schemes, typically with chains of ancilla atoms, and an interpretation algorithm to map results back to the original problem. However, interpreting approximate solutions obtained with realistic quantum computers proves to be a difficult problem. As a case study, we evaluate the ability of two interpretation strategies to correct errors in the recently introduced crossing lattice embedding. We find that one strategy, based on finding the closest embedding solution, leads to very high qualities, albeit at an exponential cost. The second strategy, based on ignoring defective regions of the embedding graph, is polynomial in the graph size, but it leads to a degradation of the solution quality which is prohibitive under realistic assumptions on the defect generation. Moreover, more favorable defect scalings lead to a contradiction with well-known approximability conjectures. Therefore, it is unlikely that a scalable and generic improvement in solution quality can be achieved with Rydberg platforms---thus moving the focus to heuristic algorithms.

arXiv:2507.22761•Physical Review A•Oct 2, 2025•3 citations

Quantum optimization on Rydberg-atom arrays with arbitrary connectivity: Gadget limitations and a heuristic approach

Pierre Cazals, Amalia Sorondo, Victor Onofre +3 more

Programmable quantum systems based on Rydberg atom arrays have recently emerged as a promising test bed for combinatorial optimization. Indeed, the maximum weighted independent set problem on unit-disk graphs can be efficiently mapped to such systems due to their geometric constraints. However, extending this capability to arbitrary graph instances typically necessitates the use of reduction gadgets, which introduce additional experimental overhead and complexity. Here, we analyze the complexity\penalty1000-\hskip0pttheoretic limits of polynomial reductions from arbitrary graphs to unit\penalty1000-\hskip0ptdisk instances. We prove any such reduction incurs a quadratic blow up in vertex count and degrades solution approximation guarantees. As a practical alternative, we propose a divide\penalty1000-\hskip0ptand\penalty1000-\hskip0ptconquer heuristic with only linear overhead, which leverages precalibrated atomic layouts. We benchmark it on Erd\"os-R\'enyi graphs, and demonstrate feasibility on the Orion Alpha processor.

arXiv:2508.06130•Physical Review A•Oct 24, 2025•5 citations
In 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 \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ-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 \ensuremathε\ensuremath{\varepsilon}\ensuremathε-approximation scheme exists.
In 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 2D 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 3D 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 ε\varepsilonε-approximation scheme exists.
In the past years, many quantum algorithms have been proposed to tackle hard combinatorial problems. These algorithms, which have been studied in depth in complexity theory, are at the heart of many industrial applications. 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 node-to-atom on such devices are limited to Unit-Disk graphs. In this setting, the inherent locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an ε-approximate solution. In this work, we present a deterministic and polynomial-time construction to embed a large family of non-local graphs in 3D atomic arrays. This construction is a first crucial step towards tackling combinatorial tasks on quantum computers for which no classical efficient ε-approximation scheme exists.
Rydberg atom arrays are a powerful platform for solving combinatorial optimization problems, owing to the Rydberg blockade mechanism, which imposes effective constraints on simultaneous atomic excitations. These constraints have enabled the encoding of the Maximum Independent Set (MIS) problem on unit disk graphs, where atoms interact within a fixed, globally defined blockade radius. However, this restriction limits the class of addressable problems. A natural extension is to consider disk graphs, which generalize unit disk graphs by allowing arbitrary disk radii and correspond to the intersection graphs of disks in the plane. Embedding such graphs in Rydberg systems requires moving beyond the standard, globally uniform blockade model. In this work, we introduce a local Rydberg blockade regime, which emerges when local drives are applied to different pairs of atoms involved in a potential interaction. We develop a general theoretical framework for this regime and propose two novel metrics, the correlation matrix and the maximum independence violation, to quantify the quality of the embedding. Using these metrics, we demonstrate that disk graphs can be meaningfully embedded into Rydberg atom arrays under local drive schemes, thereby expanding the landscape of quantum-addressable optimization problems. Finally, when evaluating approximate solutions of the MIS problem, characterized by near-optimal independent sets, local drive approaches exhibit significantly improved performance over global ones. These results highlight the practical advantage of local blockade engineering for approximate combinatorial optimization and open a path toward leveraging the analog capabilities of Rydberg platforms beyond conventional geometric constraints.
The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.
Analog quantum computing with Rydberg atoms is seen as an avenue to solve hard graph optimization problems, because they naturally encode the maximum independent set (MIS) problem on unit disk (UD) graphs, a problem that admits rather efficient approximation schemes on classical computers. Going beyond UD-MIS to address generic graphs requires embedding schemes, typically with chains of ancilla atoms, and an interpretation algorithm to map results back to the original problem. However, interpreting approximate solutions obtained with realistic quantum computers proves to be a difficult problem. As a case study, we evaluate the ability of two interpretation strategies to correct errors in the recently introduced crossing lattice embedding. We find that one strategy, based on finding the closest embedding solution, leads to very high qualities, albeit at an exponential cost. The second strategy, based on ignoring defective regions of the embedding graph, is polynomial in the graph size, but it leads to a degradation of the solution quality which is prohibitive under realistic assumptions on the defect generation. Moreover, more favorable defect scalings lead to a contradiction with well-known approximability conjectures. Therefore, it is unlikely that a scalable and generic improvement in solution quality can be achieved with Rydberg platforms---thus moving the focus to heuristic algorithms.
Programmable quantum systems based on Rydberg atom arrays have recently emerged as a promising test bed for combinatorial optimization. Indeed, the maximum weighted independent set problem on unit-disk graphs can be efficiently mapped to such systems due to their geometric constraints. However, extending this capability to arbitrary graph instances typically necessitates the use of reduction gadgets, which introduce additional experimental overhead and complexity. Here, we analyze the complexity\penalty1000-\hskip0pttheoretic limits of polynomial reductions from arbitrary graphs to unit\penalty1000-\hskip0ptdisk instances. We prove any such reduction incurs a quadratic blow up in vertex count and degrades solution approximation guarantees. As a practical alternative, we propose a divide\penalty1000-\hskip0ptand\penalty1000-\hskip0ptconquer heuristic with only linear overhead, which leverages precalibrated atomic layouts. We benchmark it on Erd\"os-R\'enyi graphs, and demonstrate feasibility on the Orion Alpha processor.