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

arXiv:2412.14976 · Physical Review Research

Quantum compilation toolkit for Rydberg atom arrays with implications for problem hardness and quantum speedups

Martin J. A. Schuetz, Ruben S. Andrist, Grant Salton, Romina Yalovetzky, Rudy Raymond, Yue Sun, Atithi Acharya, Shouvanik Chakrabarti, Marco Pistoia, Helmut G. Katzgraber

Published Jun 30, 2025• 9 citations
arXivHTMLPDF

Abstract

We propose and implement a comprehensive quantum compilation toolkit for solving the maximum independent set (MIS) problem on quantum hardware based on Rydberg atom arrays. Our end-to-end pipeline involves three core components to efficiently map generic MIS instances onto Rydberg arrays with unit-disk connectivity, with modules for graph reduction, hardware compatibility checks, and graph embedding. The first module (reducer) provides hardware-agnostic and deterministic reduction logic that iteratively reduces the problem size via lazy clique removals. We find that real-world networks can typically be reduced by orders of magnitude on subsecond timescales, thus significantly cutting down the eventual load for quantum devices. Moreover, we show that reduction techniques may be an important tool in the ongoing search for potential quantum speedups, given their ability to identify hard problem instances. In particular, for Rydberg-native MIS instances, we observe signatures of an easy-hard-easy transition and quantify a critical degree indicating the onset of a hard problem regime. The second module (compatibility checker) implements a hardware compatibility checker that quickly determines whether a given input graph may be compatible with the restrictions imposed by Rydberg quantum hardware. The third module (embedder) describes hardware-efficient graph embedding routines to generate (approximate) encodings with controllable overhead and optimized ancilla placements. We exemplify our pipeline with experiments run on the QuEra Aquila device available on Amazon Braket. In aggregate, our work provides a set of tools that extends the class of problems that can be tackled with near-term Rydberg atom arrays.

DOI
10.1103/7dkh-crjj

Related papers

Hardness of the maximum-independent-set problem on unit-disk graphs and prospects for quantum speedups

Ruben S. Andrist, Martin J. A. Schuetz, Pierre Minssen +9 more

Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi et al., Science 376, 1209 (2022)], we study the maximum-independent-set problem on unit-disk graphs with a broader range of classical solvers beyond the scope of the original paper. We carry out extensive numerical studies and assess problem hardness, using both exact and heuristic algorithms. We find that quasiplanar instances with Union-Jack-like connectivity can be solved to optimality for up to thousands of nodes within minutes, with both custom and generic commercial solvers on commodity hardware, without any instance-specific fine-tuning. We also perform a scaling analysis, showing that by relaxing the constraints on the classical simulated annealing algorithms considered in Ebadi et al., our implementation is competitive with the quantum algorithms. Conversely, instances with larger connectivity or less structure are shown to display a time-to-solution potentially orders of magnitudes larger. Based on these results, we propose protocols to systematically tune problem hardness, motivating experiments with Rydberg atom arrays on instances orders of magnitude harder (for established classical solvers) than previously studied.

arXiv:2307.09442•Physical Review Research•Dec 21, 2023•32 citations

Quantum Optimization with Arbitrary Connectivity Using Rydberg Atom Arrays

Minh-Thi Nguyen, Jin-Guo Liu, Jonathan Wurtz +3 more

Programmable quantum systems based on Rydberg atom arrays have recently been used for hardwareefficient tests of quantum optimization algorithms [Ebadi et al., Science, 376, 1209 (2022)] with hundreds of qubits.In particular, the maximum independent set problem on so-called unit-disk graphs, was shown to be efficiently encodable in such a quantum system.Here, we extend the classes of problems that can be efficiently encoded in Rydberg arrays by constructing explicit mappings from a wide class of problems to maximum-weighted independent set problems on unit-disk graphs, with at most a quadratic overhead in the number of qubits.We analyze several examples, including maximum-weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization.Numerical simulations on small system sizes indicate that the adiabatic time scale for solving the mapped problems is strongly correlated with that of the original problems.Our work provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems with arbitrary connectivity, beyond the restrictions imposed by the hardware geometry.

arXiv:2209.03965•PRX Quantum•Feb 14, 2023•119 citations

Reducibility of native weighted graphs on Rydberg Arrays

J. Kombe, J. D. Pritchard

We investigate the classical reducibility of random unit-disk graph (UDG) instances of the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems, which can be natively realised in Rydberg atom quantum processors. Using state-of-the-art kernelisation techniques, we systematically probe how far classical preprocessing can simplify such native optimisation problems of varying size and connectivity. While many small or sparse instances can be fully reduced, dense graphs often retain finite irreducible kernels even after extensive reductions. Introducing vertex weights tends to increase reducibility, whereas extending the interaction range in the underlying UDG connectivity suppresses the reduction efficiency. By exploring where classical reductions cease to be effective, we aim to delineate the regime of problem instances that remain computationally demanding - those most relevant for testing and benchmarking near-term quantum optimisation hardware. We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads, suggesting that directly running native instances may be more practical than embedding a reduced kernel.

quant-pharXiv:2605.07952•May 11, 2026•0 citations

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

Quantum optimization of maximum independent set using Rydberg atom arrays

Sepehr Ebadi, Alexander Keesling, Madelyn Cain +21 more

Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.

arXiv:2202.09372•Science•May 5, 2022•423 citations

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 +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 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.

Physical Review A•Nov 21, 2023•15 citations
We propose and implement a comprehensive quantum compilation toolkit for solving the maximum independent set (MIS) problem on quantum hardware based on Rydberg atom arrays. Our end-to-end pipeline involves three core components to efficiently map generic MIS instances onto Rydberg arrays with unit-disk connectivity, with modules for graph reduction, hardware compatibility checks, and graph embedding. The first module (reducer) provides hardware-agnostic and deterministic reduction logic that iteratively reduces the problem size via lazy clique removals. We find that real-world networks can typically be reduced by orders of magnitude on subsecond timescales, thus significantly cutting down the eventual load for quantum devices. Moreover, we show that reduction techniques may be an important tool in the ongoing search for potential quantum speedups, given their ability to identify hard problem instances. In particular, for Rydberg-native MIS instances, we observe signatures of an easy-hard-easy transition and quantify a critical degree indicating the onset of a hard problem regime. The second module (compatibility checker) implements a hardware compatibility checker that quickly determines whether a given input graph may be compatible with the restrictions imposed by Rydberg quantum hardware. The third module (embedder) describes hardware-efficient graph embedding routines to generate (approximate) encodings with controllable overhead and optimized ancilla placements. We exemplify our pipeline with experiments run on the QuEra Aquila device available on Amazon Braket. In aggregate, our work provides a set of tools that extends the class of problems that can be tackled with near-term Rydberg atom arrays.
Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi et al., Science 376, 1209 (2022)], we study the maximum-independent-set problem on unit-disk graphs with a broader range of classical solvers beyond the scope of the original paper. We carry out extensive numerical studies and assess problem hardness, using both exact and heuristic algorithms. We find that quasiplanar instances with Union-Jack-like connectivity can be solved to optimality for up to thousands of nodes within minutes, with both custom and generic commercial solvers on commodity hardware, without any instance-specific fine-tuning. We also perform a scaling analysis, showing that by relaxing the constraints on the classical simulated annealing algorithms considered in Ebadi et al., our implementation is competitive with the quantum algorithms. Conversely, instances with larger connectivity or less structure are shown to display a time-to-solution potentially orders of magnitudes larger. Based on these results, we propose protocols to systematically tune problem hardness, motivating experiments with Rydberg atom arrays on instances orders of magnitude harder (for established classical solvers) than previously studied.
Programmable quantum systems based on Rydberg atom arrays have recently been used for hardwareefficient tests of quantum optimization algorithms [Ebadi et al., Science, 376, 1209 (2022)] with hundreds of qubits.In particular, the maximum independent set problem on so-called unit-disk graphs, was shown to be efficiently encodable in such a quantum system.Here, we extend the classes of problems that can be efficiently encoded in Rydberg arrays by constructing explicit mappings from a wide class of problems to maximum-weighted independent set problems on unit-disk graphs, with at most a quadratic overhead in the number of qubits.We analyze several examples, including maximum-weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization.Numerical simulations on small system sizes indicate that the adiabatic time scale for solving the mapped problems is strongly correlated with that of the original problems.Our work provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems with arbitrary connectivity, beyond the restrictions imposed by the hardware geometry.
We investigate the classical reducibility of random unit-disk graph (UDG) instances of the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems, which can be natively realised in Rydberg atom quantum processors. Using state-of-the-art kernelisation techniques, we systematically probe how far classical preprocessing can simplify such native optimisation problems of varying size and connectivity. While many small or sparse instances can be fully reduced, dense graphs often retain finite irreducible kernels even after extensive reductions. Introducing vertex weights tends to increase reducibility, whereas extending the interaction range in the underlying UDG connectivity suppresses the reduction efficiency. By exploring where classical reductions cease to be effective, we aim to delineate the regime of problem instances that remain computationally demanding - those most relevant for testing and benchmarking near-term quantum optimisation hardware. We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads, suggesting that directly running native instances may be more practical than embedding a reduced kernel.
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.
Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.
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.