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:2503.17115 · Physical Review Applied

Sparse-graph optimization using weighted quantum wires in Rydberg-atom arrays

André Gonçalves de Oliveira, Johannes Kombe, G. Pelegrí, Paul Schroff, M. T. Wells-Pestell, D. M. Walker, Andrew J. Daley, Jonathan D. Pritchard

Published Jul 6, 2026• 0 citations
arXivHTMLPDF

Abstract

Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. Here we present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms, which we call quantum wires, to natively embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture. For graphs with quasi-unit-disk connectivity, in which only a few long-range edges are required, our approach requires a significantly lower overhead in the number of ancilla qubits than previous proposals, facilitating the implementation on currently available hardware. To demonstrate the approach, we perform annealing of weighted graphs on a programmable atom array using local light shifts to encode problem-specific weights across graphs of varying sizes. This approach successfully identifies the solutions to the original MWIS and QUBO graph instances. Our work expands the operational toolkit of near-term neutral atom arrays, enhancing their potential for scalable quantum optimization.

DOI
10.1103/bxsl-f1zc

Related papers

Quantum optimization with globally driven neutral atom arrays

Martin Lanthaler, Kilian Ender, Davit Khachatryan +5 more

Neutral atoms trapped in configurable tweezer arrays are a promising platform for solving hard optimization problems. While such platforms natively embed unit-disk maximum weight independent set (UD-MWIS) problems, general problem classes require an embedding that maps them onto UD-MWIS instances. Implementing the necessary asymmetric weights has so far required local control of detunings at each atom. Here, we demonstrate quantum optimization using strictly global driving fields, eliminating the need for local field control. Instead, to effectively implement the required local detunings we exploit weak Rydberg interactions---too weak to generate Rydberg blockade but strong enough to effectively induce the required local detunings. For this, we introduce the concept of precisely placed anchor atoms that impose controlled energy shifts on nearby atoms which can be effectively considered as induced local detunings. We demonstrate that parity-architecture-based neutral atom embeddings of general optimization problems allow for a successful anchor placement strategy, such that all demanded local fields can be replaced by anchors. We experimentally demonstrate this concept on a Pasqal Orion Alpha machine and benchmark all standard building blocks. Finally, we solve quadratic unconstrained binary optimization (QUBO) problems on four-node all-to-all connected graphs embedded in a 43-atom array using seven precisely-placed anchor atoms. By removing the requirement for local addressing, our work overcomes a major experimental bottleneck in solving optimization problems on neutral-atom quantum hardware and can be readily integrated into existing platforms.

arXiv:2410.03902•Oct 4, 2024•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

Demonstration of Weighted-Graph Optimization on a Rydberg-Atom Array Using Local Light Shifts

André Gonçalves de Oliveira, E. Diamond-Hitchcock, D. M. Walker +7 more

Neutral-atom arrays have emerged as a versatile platform toward scalable quantum computation and optimization. In this paper, we present demonstrations of solving maximum-weighted independent-set problems on a Rydberg-atom array using annealing with local light shifts. We verify the ability to prepare weighted graphs in one-dimensional (1D) and two-dimensional (2D) arrays, including embedding a five-vertex nonunit-disk graph using nine physical qubits and demonstration of a simple crossing gadget. We find common annealing ramps leading to preparation of the target ground state robustly over a substantial range of different graph weightings. This work provides a route to exploring large-scale optimization of nonplanar weighted graphs relevant for solving relevant real-world problems.

arXiv:2404.02658•PRX Quantum•Jan 2, 2025•24 citations

Graph coloring via quantum optimization on a Rydberg-qudit atom array

Toonyawat Angkhanawin, Aydin Deger, Jonathan D. Pritchard +1 more

Abstract Neutral atom arrays have emerged as a versatile candidate for the embedding of hard classical optimization problems. Prior work has focused on mapping problems onto finding the maximum independent set of weighted or unweighted unit disk graphs. In this paper we introduce a new approach to solving natively-embedded vertex graph coloring problems by performing coherent annealing with Rydberg-qudit atoms, where different same-parity Rydberg levels represent a distinct label or color. We demonstrate the ability to robustly find optimal graph colorings for chromatic numbers up to the number of distinct Rydberg states used, in our case k = 3. We analyze the impact of both the long-range potential tails and residual inter-state interactions, proposing encoding strategies that suppress errors in the resulting ground states. We discuss the experimental feasibility of this approach and propose extensions to solve higher chromatic number problems, providing a route towards direct solution of a wide range of real-world integer optimization problems using near-term neutral atom hardware.

arXiv:2504.08598•Quantum Science and Technology•Jan 21, 2026•1 citation

Rydberg-Blockade-Based Parity Quantum Optimization

Martin Lanthaler, Clemens Dlaska, Kilian Ender +1 more

We present a scalable architecture for solving higher-order constrained binary optimization (HCBO) problems on current neutral-atom hardware operating in the Rydberg blockade regime. In particular, we formulate the recently developed parity encoding of arbitrary connected HCBO problems as a maximum-weight independent set (MWIS) problem on disk graphs, that are directly encodable on such devices. Our architecture builds from small MWIS modules in a problem-independent way, crucial for practical scalability.

arXiv:2210.05604•Physical Review Letters•May 30, 2023•32 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
Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. Here we present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms, which we call quantum wires, to natively embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture. For graphs with quasi-unit-disk connectivity, in which only a few long-range edges are required, our approach requires a significantly lower overhead in the number of ancilla qubits than previous proposals, facilitating the implementation on currently available hardware. To demonstrate the approach, we perform annealing of weighted graphs on a programmable atom array using local light shifts to encode problem-specific weights across graphs of varying sizes. This approach successfully identifies the solutions to the original MWIS and QUBO graph instances. Our work expands the operational toolkit of near-term neutral atom arrays, enhancing their potential for scalable quantum optimization.
Neutral atoms trapped in configurable tweezer arrays are a promising platform for solving hard optimization problems. While such platforms natively embed unit-disk maximum weight independent set (UD-MWIS) problems, general problem classes require an embedding that maps them onto UD-MWIS instances. Implementing the necessary asymmetric weights has so far required local control of detunings at each atom. Here, we demonstrate quantum optimization using strictly global driving fields, eliminating the need for local field control. Instead, to effectively implement the required local detunings we exploit weak Rydberg interactions---too weak to generate Rydberg blockade but strong enough to effectively induce the required local detunings. For this, we introduce the concept of precisely placed anchor atoms that impose controlled energy shifts on nearby atoms which can be effectively considered as induced local detunings. We demonstrate that parity-architecture-based neutral atom embeddings of general optimization problems allow for a successful anchor placement strategy, such that all demanded local fields can be replaced by anchors. We experimentally demonstrate this concept on a Pasqal Orion Alpha machine and benchmark all standard building blocks. Finally, we solve quadratic unconstrained binary optimization (QUBO) problems on four-node all-to-all connected graphs embedded in a 43-atom array using seven precisely-placed anchor atoms. By removing the requirement for local addressing, our work overcomes a major experimental bottleneck in solving optimization problems on neutral-atom quantum hardware and can be readily integrated into existing platforms.
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.
Neutral-atom arrays have emerged as a versatile platform toward scalable quantum computation and optimization. In this paper, we present demonstrations of solving maximum-weighted independent-set problems on a Rydberg-atom array using annealing with local light shifts. We verify the ability to prepare weighted graphs in one-dimensional (1D) and two-dimensional (2D) arrays, including embedding a five-vertex nonunit-disk graph using nine physical qubits and demonstration of a simple crossing gadget. We find common annealing ramps leading to preparation of the target ground state robustly over a substantial range of different graph weightings. This work provides a route to exploring large-scale optimization of nonplanar weighted graphs relevant for solving relevant real-world problems.
Abstract Neutral atom arrays have emerged as a versatile candidate for the embedding of hard classical optimization problems. Prior work has focused on mapping problems onto finding the maximum independent set of weighted or unweighted unit disk graphs. In this paper we introduce a new approach to solving natively-embedded vertex graph coloring problems by performing coherent annealing with Rydberg-qudit atoms, where different same-parity Rydberg levels represent a distinct label or color. We demonstrate the ability to robustly find optimal graph colorings for chromatic numbers up to the number of distinct Rydberg states used, in our case k = 3. We analyze the impact of both the long-range potential tails and residual inter-state interactions, proposing encoding strategies that suppress errors in the resulting ground states. We discuss the experimental feasibility of this approach and propose extensions to solve higher chromatic number problems, providing a route towards direct solution of a wide range of real-world integer optimization problems using near-term neutral atom hardware.
We present a scalable architecture for solving higher-order constrained binary optimization (HCBO) problems on current neutral-atom hardware operating in the Rydberg blockade regime. In particular, we formulate the recently developed parity encoding of arbitrary connected HCBO problems as a maximum-weight independent set (MWIS) problem on disk graphs, that are directly encodable on such devices. Our architecture builds from small MWIS modules in a problem-independent way, crucial for practical scalability.
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.