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:2604.27030 · Physical Review Research

Efficient mapping of multi-constraint satisfaction problems to Rydberg platforms

Robert Gloeckner, Shahram Panahiyan, Frederik Koch, Dieter Jaksch, Joseph Doetsch

quant-phSubmitted Apr 29, 2026• Announced Apr 30, 2026• 0 citations
arXivHTMLPDF

Abstract

We present a hardware-native gadget framework for solving constraint satisfaction problems on Rydberg quantum computing architectures. Our approach introduces a compact $xor_1$ gadget that enforces exactly-one constraints, ubiquitous in combinatorial optimization, directly through geometric embedding and blockade interactions. A key advantage of the $xor_1$ gadget is its fixed, problem-size-independent detuning requirements: enforcing constraints through blockade interactions eliminates the need for large penalty terms, thereby substantially reducing the detuning range compared to Quadratic Unconstrained Binary Optimization (QUBO) formulations and improving experimental feasibility. By tailoring the construction to the geometric connectivity of Rydberg atom arrays, the framework bypasses the all-to-all physical couplings often assumed in logical encodings. This enables embeddings compatible with planar layouts and avoids highly connected arrangements. We develop scalable implementations that reduce atom count and connectivity overhead while avoiding extensive classical preprocessing, making them compatible with near-term neutral-atom hardware. As illustrations, we apply our framework to the gate-assignment and $N$-queens problems, highlighting its practicality, resource efficiency, and hardware compatibility. In these examples, we observe reductions in detuning range of up to $99\%$ and savings in atom count and connectivity overhead of up to $54\%$ compared to the QUBO method. These results establish a route toward implementing large-scale combinatorial optimization on Rydberg platforms beyond the limits of existing encodings.

Comments
24 pages, 17 figures, 10 tables

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

Encoding Circuit Satisfiability in Rydberg Atom Arrays

Haotian Ji, Zhangjie Qin, Zheng An +6 more

Rydberg atom arrays natively encode the maximum-weight independent set (MWIS) problem through the blockade mechanism, so the Boolean circuit satisfiability problem (Circuit-SAT) can be brought onto the platform once it is reduced to MWIS. The conventional encoding of Circuit-SAT in the Rydberg atom array proceeds through conjunctive normal form (CNF) and incurs a substantial atom overhead. We introduce CAMERA (Circuit-SAT Atom-efficient MWIS Encoding for Rydberg Arrays), a method that provides MWIS encodings of Circuit-SAT instances on the king subgraph geometry of the array. CAMERA represents each logic gate as a compact weighted gadget and assembles the gadgets with a placement and routing compiler inspired by very large scale integration (VLSI) design. On random multi-gate benchmarks, the direct encoding route lowers the atom cost relative to the CNF route by an average factor of $22.4 \pm 1.8$. To demonstrate that the encoding extends from individual weighted gadgets to multi-gate arithmetic blocks, we compile a full adder and a multiplier, verifying each against its complete truth table by exact classical ground state calculations. We further showcase solving a representative Circuit-SAT instance end-to-end, from gate level compilation through a closed-system tensor-network simulation of a hardware-compatible annealing protocol on the encoded 30-atom instance to readout of a satisfying assignment. These results establish a complete encoding and simulation workflow as a proof of principle, and a concrete route toward solving a broader family of combinatorial problems on Rydberg atom arrays.

quant-pharXiv:2608.12938•Aug 14, 2026•0 citations

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

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

Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization

Shashank Sanjay Bhat, Peiyong Wang, Joseph West +1 more

Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.

quant-pharXiv:2602.07357•Feb 10, 2026•0 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
We present a hardware-native gadget framework for solving constraint satisfaction problems on Rydberg quantum computing architectures. Our approach introduces a compact xor1xor_1xor1​ gadget that enforces exactly-one constraints, ubiquitous in combinatorial optimization, directly through geometric embedding and blockade interactions. A key advantage of the xor1xor_1xor1​ gadget is its fixed, problem-size-independent detuning requirements: enforcing constraints through blockade interactions eliminates the need for large penalty terms, thereby substantially reducing the detuning range compared to Quadratic Unconstrained Binary Optimization (QUBO) formulations and improving experimental feasibility. By tailoring the construction to the geometric connectivity of Rydberg atom arrays, the framework bypasses the all-to-all physical couplings often assumed in logical encodings. This enables embeddings compatible with planar layouts and avoids highly connected arrangements. We develop scalable implementations that reduce atom count and connectivity overhead while avoiding extensive classical preprocessing, making them compatible with near-term neutral-atom hardware. As illustrations, we apply our framework to the gate-assignment and NNN-queens problems, highlighting its practicality, resource efficiency, and hardware compatibility. In these examples, we observe reductions in detuning range of up to 99%99\%99% and savings in atom count and connectivity overhead of up to 54%54\%54% compared to the QUBO method. These results establish a route toward implementing large-scale combinatorial optimization on Rydberg platforms beyond the limits of existing encodings.
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.
Rydberg atom arrays natively encode the maximum-weight independent set (MWIS) problem through the blockade mechanism, so the Boolean circuit satisfiability problem (Circuit-SAT) can be brought onto the platform once it is reduced to MWIS. The conventional encoding of Circuit-SAT in the Rydberg atom array proceeds through conjunctive normal form (CNF) and incurs a substantial atom overhead. We introduce CAMERA (Circuit-SAT Atom-efficient MWIS Encoding for Rydberg Arrays), a method that provides MWIS encodings of Circuit-SAT instances on the king subgraph geometry of the array. CAMERA represents each logic gate as a compact weighted gadget and assembles the gadgets with a placement and routing compiler inspired by very large scale integration (VLSI) design. On random multi-gate benchmarks, the direct encoding route lowers the atom cost relative to the CNF route by an average factor of 22.4±1.822.4 \pm 1.822.4±1.8. To demonstrate that the encoding extends from individual weighted gadgets to multi-gate arithmetic blocks, we compile a full adder and a multiplier, verifying each against its complete truth table by exact classical ground state calculations. We further showcase solving a representative Circuit-SAT instance end-to-end, from gate level compilation through a closed-system tensor-network simulation of a hardware-compatible annealing protocol on the encoded 30-atom instance to readout of a satisfying assignment. These results establish a complete encoding and simulation workflow as a proof of principle, and a concrete route toward solving a broader family of combinatorial problems on Rydberg atom arrays.
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.
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.
Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.
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.