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:2508.06130 · Physical Review A

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

Pierre Cazals, Amalia Sorondo, Victor Onofre, Constantin Dalyac, Wesley da Silva Coelho, Vittorio Vitale

Published Oct 24, 2025• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/3sjz-gfmr

Related papers

Error-Corrected Quantum Optimization via Rydberg Atom Array Embeddings

Andrew Byun, Berend Klaver, Arinjoy De +5 more

Rydberg atom quantum optimizers naturally encode the maximum independent set problem on geometric graphs. However, to solve general combinatorial optimization problems on more complex topologies, an embedding is required to overcome the limited-range native interactions. Such embeddings use gadgets, specific arrangements of atoms, which inevitably introduce ancillary atoms. Here, we show that this apparent overhead instead provides an intrinsic resource for error correction. Specifically, we demonstrate that the Parity Architecture-based Rydberg embedding naturally forms a classical error-correcting code, a principle that extends to other Rydberg blockade-based embeddings. Within superatom substructures, exact Rydberg-excitation-number constraints provide local error syndromes at no additional hardware cost and give rise to a strictly nonlinear code. To correct bit-flip errors, we introduce the precisely tailored Cluster decoder, which exploits these local constraints and the underlying gadget structure. Numerically, this approach achieves an error threshold of $p_{\text{th}}\gtrsim26 \%$ across different layout geometries. Experimentally, on the QuEra Aquila QPU, the Cluster decoder recovers exact optimization solutions with an average success rate of $\gtrsim8\%$ for systems of up to 107 atoms, even when bare hardware and standard greedy post-processing find none. A Rydberg atom array embedding is therefore not merely a hardware mapping of an optimization problem, but a co-designed architecture for quantum optimization in which embedding, computation, and error correction emerge from the same physical structure.

quant-pharXiv:2610.39670•Oct 30, 2026•0 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

Optimization of Quantum Encoding for Combinatorial Problems in Rydberg Atom Array

Jiale Liu, Yikang Zhu, Qiang Zheng +2 more

Programmable quantum systems utilizing Rydberg atoms have recently been shown to efficiently encode combinatorial optimization problems. The relationships among the variables in these optimization problems can be transformed into a maximum weighted independent set problem within the Rydberg atom system, requiring at most a quadratic overhead in terms of the number of qubits. Although experiments with current Rydberg quantum systems have demonstrated linear speedup compared to classical algorithms, the overhead in both the number of qubits and time remains substantial. To further reduce the overhead of encoding these optimization problems in Rydberg atom systems, we propose a simplification strategy and design a new heuristic algorithm that incorporates a topological sort approach to optimize the encoding process. We conduct extensive experiments on small graphs with dozens of qubits. The numerical results demonstrate the effectiveness of our algorithm in both runtime and optimization efficiency. Specifically, our algorithm reduces the number of required encoding qubits by 12.0% compared to existing methods. Additionally, our approach reduces the time complexity to a quadratic overhead, enabling experiments on larger graphs. The results further indicate that our algorithm provides significant time advantages over existing solutions.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 31, 2025•0 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

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
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.
Rydberg atom quantum optimizers naturally encode the maximum independent set problem on geometric graphs. However, to solve general combinatorial optimization problems on more complex topologies, an embedding is required to overcome the limited-range native interactions. Such embeddings use gadgets, specific arrangements of atoms, which inevitably introduce ancillary atoms. Here, we show that this apparent overhead instead provides an intrinsic resource for error correction. Specifically, we demonstrate that the Parity Architecture-based Rydberg embedding naturally forms a classical error-correcting code, a principle that extends to other Rydberg blockade-based embeddings. Within superatom substructures, exact Rydberg-excitation-number constraints provide local error syndromes at no additional hardware cost and give rise to a strictly nonlinear code. To correct bit-flip errors, we introduce the precisely tailored Cluster decoder, which exploits these local constraints and the underlying gadget structure. Numerically, this approach achieves an error threshold of pth≳26%p_{\text{th}}\gtrsim26 \%pth​≳26% across different layout geometries. Experimentally, on the QuEra Aquila QPU, the Cluster decoder recovers exact optimization solutions with an average success rate of ≳8%\gtrsim8\%≳8% for systems of up to 107 atoms, even when bare hardware and standard greedy post-processing find none. A Rydberg atom array embedding is therefore not merely a hardware mapping of an optimization problem, but a co-designed architecture for quantum optimization in which embedding, computation, and error correction emerge from the same physical structure.
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.
Programmable quantum systems utilizing Rydberg atoms have recently been shown to efficiently encode combinatorial optimization problems. The relationships among the variables in these optimization problems can be transformed into a maximum weighted independent set problem within the Rydberg atom system, requiring at most a quadratic overhead in terms of the number of qubits. Although experiments with current Rydberg quantum systems have demonstrated linear speedup compared to classical algorithms, the overhead in both the number of qubits and time remains substantial. To further reduce the overhead of encoding these optimization problems in Rydberg atom systems, we propose a simplification strategy and design a new heuristic algorithm that incorporates a topological sort approach to optimize the encoding process. We conduct extensive experiments on small graphs with dozens of qubits. The numerical results demonstrate the effectiveness of our algorithm in both runtime and optimization efficiency. Specifically, our algorithm reduces the number of required encoding qubits by 12.0% compared to existing methods. Additionally, our approach reduces the time complexity to a quadratic overhead, enabling experiments on larger graphs. The results further indicate that our algorithm provides significant time advantages over existing solutions.
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.
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.