Efficient mapping of multi-constraint satisfaction problems to Rydberg platforms
Robert Gloeckner 1, Shahram Panahiyan 2,3, Frederik Koch 2, Dieter Jaksch 2,4,5, Joseph Doetsch 1 · 2026
Read Efficient mapping of multi-constraint satisfaction problems to Rydberg platforms by Robert Gloeckner 1, Shahram Panahiyan 2,3, Frederik Koch 2, Dieter Jaksch 2,4,5, Joseph Doetsch 1 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-27030.txt.
Introduction
Gloeckner and four colleagues present a hardware-native gadget framework for constraint problems on Rydberg quantum hardware. A compact xor gadget enforces one-hot constraints through geometric embedding and blockade, with fixed detuning. Skipping penalty terms cuts tuning versus QUBO and improves feasibility, while geometry bypasses all-to-all couplings and fits planar layouts. Lean designs cut atom counts with little preprocessing, suiting near-term hardware. On gate assignment and N-queens, it cuts detuning by up to 99 percent and atoms and links by up to 54 percent.
Catalog record
| CREATOR | Robert Gloeckner 1, Shahram Panahiyan 2,3, Frederik Koch 2, Dieter Jaksch 2,4,5, Joseph Doetsch 1 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121461 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.27030
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient mapping of multi-constraint satisfaction problems to Rydberg platforms Robert Gloeckner 1, Shahram Panahiyan 2,3, Frederik Koch 2, Dieter Jaksch 2,4,5, Joseph Doetsch 1 Abstract We present a hardware-native gadget framework for solving constraint satisfaction problems on Rydberg quantum computing architectures. Our approach introduces a compact x o r 1 xor_{1} gadget that enforces exactly-one constraints, ubiquitous in combinatorial optimization, directly through geometric embedding and blockade interactions. A key advantage of the x o r 1 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 N -queens problems, highlighting its practicality, resource efficiency, and hardware compatibility. In these examples, we observe reductions in detuning range of up to 99 % 99\% and savings in atom count and connectivity overhead of up to 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. I Introduction Optimization and constraint satisfaction problems (CSP) are central challenges in many industrial and engineering applications, including portfolio optimization, logistics, scheduling, and design problems 34 ; 10 ; 37 . Such tasks typically involve searching large, complex, and often non-convex or constrained solution spaces, where classical heuristics, gradient-based methods, and mathematical programming approaches can face significant computational limitations as problem size increases 11 . In many cases, the exponential growth of the solution space renders the identification of feasible or optimal solutions computationally intractable, even with advanced relaxation and approximation techniques 7 ; 19 ; 46 . Emerging quantum computing technologies offer a new paradigm for tackling such problems 1 ; 45 ; 23 . By exploiting quantum superposition and entanglement, quantum algorithms may enable new strategies for exploring complex optimization landscapes beyond classical capabilities 18 ; 1 ; 28 . As quantum hardware advances, integrating quantum methods into optimization workflows could accelerate solutions to previously intractable problems across scientific and industrial domains 8 ; 39 ; 38 ; 42 . A particularly promising direction within this landscape is the use of controlled quantum many-body dynamics as a computational resource 16 ; 4 ; 40 ; 17 ; 12 ; 32 ; 5 ; 43 ; 31 ; 26 ; 6 ; 33 ; 29 . In this paradigm, the evolution of a quantum system is engineered such that its final state encodes the solution to a target optimization problem or CSP. Rydberg-atom quantum computing platforms are especially well suited to this approach: the Rydberg blockade mechanism naturally implements interactions on unit-disk graphs (UDGs), enabling the direct embedding of maximum-weighted independent set (MWIS) problems into the native many-body Hamiltonian 36 ; 15 ; 30 . This native correspondence between physical interactions and graph-theoretic constraints distinguishes Rydberg arrays from more abstract gate-based optimization implementations. Building on this observation, Nguyen et al. introduced a family of gadget constructions that significantly broaden the class of combinatorial optimization problems and CSPs realizable on Rydberg atom arrays (RAAs) 35 . While powerful, existing implementations face important practical challenges. QUBO-based formulations typically enforce hard constraints through large energetic penalties, leading to significant overhead in system size and requiring substantial classical preprocessing to generate the corresponding embeddings. Moreover, the large detunings required to impose such penalties consume a substantial fraction of the finite detuning range available in current Rydberg platforms. As a result, the available dynamic range must be shared between enforcing constraints and encoding the cost function, limiting the energy scale separation between feasible and infeasible configurations as well as between competing feasible solutions. This compression reduces spectral distinguishability, increasing sensitivity to noise and control imperfections 16 ; 40 ; 13 ; 3 ; 41 . Together, these effects hinder both the faithful realization of constraints and the accurate representation of the optimization landscape, ultimately limiting scalability and solution quality. In this work, we introduce a gadget-based framework, the xor_{1} gadget, that addresses these limitations by reformulating constraint satisfaction problems using clique-based constructions that map efficiently onto Rydberg architectures. Our primary focus is on solving CSPs, while we also briefly discuss extending the framework to optimization which is conceptually straightforward. The paper is organized as follows. Section II presents the main results. Section III details the mathematical description of the xor_{1} formulation, including the clique graph representation, its Boolean optimization reformulation, and multi-constraint reduction via the xor_{1} encoding. Section IV covers the mapping of cliques to unit-disk graphs and Rydberg platforms. Section V introduces the xor_{1} gadget and composite structures, including gadget construction, utilization of crossing and copy gadgets, MWIS analysis, realization of conjunctions, scaling analysis, and generalization from constraint satisfaction to optimization. Section VI presents a minimal example of gate assignment. Section VII concludes, with the Appendix providing larger gate-assignment illustrations ( IX.1 ) and the N -queens problem ( IX.1 ) realization via xor_{1} gadget. II Main results The central ideas of this work are summarized schematically in Fig. 1 . We introduce a xor_{1} gadget that enables the solution of binary optimization problems and CSPs with exactly-one and zero-or-one constraints within a clique-based incompatibility-graph formalism (Sec. III ). In this framework, cliques represent collections of mutually exclusive assignments that enforce selection constraints. These clique-based constructions can be embedded as subgraphs of UDGs, whose MWIS formulation maps directly to problem instances realizable on RAAs (Sec. IV ). Leveraging this correspondence, we design geometric xor_{1} gadgets that encode exactly-one and zero-or-one constraints through blockade interactions and Rydberg atom arrangements rather than energetic penalty terms. The advantages of the proposed xor_{1} gadget over existing approaches are fourfold. Example I Example II Example III gates 3 3 5 slots 7 10 15 flights 5 10 20 opt. var. 13 26 81 xor_{1} -detuning 6 6 6 QUBO-detuning 416 1320 9156 xor_{1} -atoms 2693 8119 57124 QUBO-atoms 3076 10298 89696 Table 1: Comparison of three gate-assignment example scenarios using the proposed xor_{1} gadget in this work and the QUBO-based method introduced in Ref. 35 . The increasing number of optimization variables (opt. var.) reflects the growing number of flights to be assigned to gates under time-slot and geometric restrictions (see Sec. IX.1 for details). The xor_{1} - and QUBO-detuning correspond to the maximum range of Rydberg atom detunings required for the array to enforce feasible solutions and satisfy all constraints. Detuning values are reported in dimensionless units normalized by the characteristic Rabi frequency \Omega_{0} 35 , which we set to \Omega_{0}=1 for convenience. The quantities labeled xor_{1} -atoms and QUBO-atoms denote the number of Rydberg atoms required to implement the corresponding RAA encodings. First, the detuning requirements of the xor_{1} gadget are fixed and independent of problem size, unlike penalty-based encodings such as Ref. 35