Efficient mapping of multi-constraint satisfaction problems to Rydberg platforms

Gloeckner, Panahiyan, Koch, Jaksch, Doetsch · arXiv:2604.27030 · 2026-05-01 (new submission, quant-ph) · score 8/10 (HIGH) · ← Back to digest

Abstract

We present a hardware-native gadget framework for solving constraint satisfaction problems on Rydberg quantum computing architectures. Our approach introduces a compact xor₁ gadget that enforces exactly-one constraints, ubiquitous in combinatorial optimization, directly through geometric embedding and blockade interactions. A key advantage of the xor₁ 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 QUBO formulations and improving experimental feasibility. By tailoring the construction to the geometric connectivity of Rydberg atom arrays, the framework bypasses all-to-all physical couplings often assumed in logical encodings, enabling embeddings compatible with planar layouts. Applied to gate-assignment and N-queens problems, the framework gives detuning-range reductions up to 99% and atom-count savings up to 54% compared to the QUBO method.

Executive summary

The authors introduce a Rydberg-native xor₁ gadget that encodes the ubiquitous "exactly one of these variables is true" constraint geometrically — through Rydberg blockade — instead of via QUBO penalty terms. This is conceptually identical to Yuan's Y2 strategy of replacing QUBO penalties with hard, constraint-preserving mixers (their quasi-binary encoding kept feasibility through the mixer; this paper keeps it through the array geometry). Empirically the construction reduces required detuning by up to 99% and atom count by up to 54% relative to the standard QUBO gadget of Nguyen et al. (2023). Demonstrated on airport gate-assignment and N-queens, two cardinality-constrained CSPs that share the structural flavour of Y2's portfolio cardinality constraints and Y4's k-out-of-n feasibility.

Main contribution

The paper formulates constraint satisfaction as a maximum-weight independent set (MWIS) on a unit-disk graph (UDG) — Rydberg's native problem — and supplies a compact gadget (one unit cell of nine atoms) that enforces a single exactly-one constraint geometrically. The gadget composes via dedicated "copy" and "crossing" sub-gadgets so that arbitrary Boolean conjunctions of exactly-one constraints embed into a planar Rydberg array. Detuning values are constants (≤ 6 Ω₀), independent of problem size, in contrast to QUBO penalties which scale with the problem (up to 9156 Ω₀ for the largest gate-assignment instance studied). Atom-count scaling is O(m·N) versus O(N²) for the QUBO encoding, where m is the number of constraints and N the number of optimisation variables.

Key constructions and results

Clique formulation (Sec. III): CSPs are recast as maximum-weight cliques on an incompatibility graph; cliques become MWIS on the complement and embed onto UDG.
xor₁ gadget (Sec. V.A): a dedicated unit-cell of Rydberg atoms whose ground state encodes a single exactly-one constraint, with vertex weights chosen so that activating exactly one optimisation atom is energetically degenerate with all infeasible configurations excluded.
Composite-structure construction (Sec. V.B–D): "copy" gadgets propagate a logical variable through a 1D chain of atoms; "crossing" gadgets allow logical wires to pass through one another without unwanted couplings, jointly enabling planar embedding of arbitrary multi-constraint CSPs.
Scaling analysis (Sec. V.E): total atom count scales as O(mN) — closer to the linear-in-m ideal than the quadratic O(N²) Nguyen-style construction.
Benchmarks (Sec. VI–Appendix): on three gate-assignment instances (3 gates × 7 slots × 5 flights up to 5 gates × 15 slots × 20 flights), atom count drops by up to 37% and detuning by > 99% versus the QUBO encoding; on N-queens the atom-count saving reaches 54%.

Detailed walkthrough

The starting point (Sec. II–III) is the observation that constraint satisfaction problems can be recast as cliques in an "incompatibility graph": each variable–value assignment is a vertex, edges connect mutually exclusive assignments, and a clique selects exactly one element per cluster of mutually exclusive vertices. Translating cliques to MWIS on the complement — which is the native problem for Rydberg blockade — provides an immediate physical embedding. The catch is that arbitrary incompatibility graphs are not unit-disk; they require all-to-all logical connectivity that does not match Rydberg's geometry-bound interaction. The paper's main technical work is showing how to realise this connectivity with planar geometric gadgets and blockade alone.

Section V.A introduces the xor₁ unit cell: a small number of dummy atoms arranged so that the unique highest-weight independent set of the cell corresponds to "exactly one optimisation atom is active." The key parameter choice is that the detuning required to enforce the constraint is fixed at δ = 6 in units of the Rabi frequency Ω₀, regardless of how large the problem grows. This contrasts sharply with the QUBO formulation, where each constraint contributes a penalty term scaling like k(k−1)/2 to make the constraint dominate the cost function. Table I in the paper reports detuning ranges of 416, 1320, and 9156 for the three QUBO benchmark cases — orders of magnitude larger than the Rydberg detuning bandwidth available on current neutral-atom platforms. The xor₁ gadget keeps the available detuning budget free for encoding the actual cost function, which the authors argue is decisive for the spectral separation between feasible and infeasible configurations and therefore for solution fidelity.

Sections V.B–D develop the composite construction. A "copy" gadget propagates the logical state of one optimisation atom along a 1D chain of dummy atoms — needed because each variable typically appears in many constraints, but in a planar geometry each atom can directly couple only to a limited neighbourhood. A "crossing" gadget allows two logical wires to cross planarly without coupling. With these two building blocks plus the xor₁ unit cell, arbitrary collections of exactly-one constraints can be embedded as MWIS instances on a unit-disk graph that fits a planar Rydberg layout. Section V.E gives the scaling: m constraints over N variables require O(mN) atoms, versus the O(N²) of the standard QUBO mapping. Importantly, this scaling is achieved without classical preprocessing — a complaint the authors make about the Nguyen-style approach, where minor-embedding solvers add nontrivial wall-clock time.

Section VI applies the framework to airport gate-assignment, an exactly-one-per-time-slot scheduling problem with hard side-constraints (e.g. some gates can only serve narrow-body aircraft). The minimal example has 4 flights, 3 gates, and a small number of slots; it is laid out atom-by-atom (Figs. 13–15) to demonstrate that the ground state of the resulting RAA encodes a feasible flight allocation. Three larger instances (Examples I, II, III in Table I) have up to 81 binary optimisation variables; for each, the xor₁ framework gives a planar embedding requiring far fewer atoms and a vastly smaller detuning range than the QUBO encoding (Table I: 9156 → 6 detuning, 89696 → 57124 atoms for Example III).

Appendix VIII.B applies the same construction to N-queens, the canonical CSP of placing N non-attacking queens on an N×N board. Because every row, column, and diagonal must contain exactly one queen, the problem is a natural target for an exactly-one gadget framework. The resulting xor₁ embedding cuts atom count by 54% relative to the QUBO encoding while keeping the detuning at the same fixed value of 6. The authors note that this size reduction translates directly into better fidelity on real Rydberg devices, where atom number and coherence trade off.

Figures

Cliques in incompatibility graph — Cliques in the incompatibility graph for a small CSP: vertices are variable–value assignments, edges encode mutual exclusion, and cliques correspond to subsets of fully connected vertices (one per "exactly-one" constraint).

xor1 active configurations — Active and inactive configurations of the xor₁ unit cell, illustrating that the gadget penalises configurations with more than one optimisation atom active while leaving exactly-one configurations as ground states.

xor1 gadget — Geometric structure of the xor₁ gadget on the Rydberg array: dummy atoms surrounding optimisation atoms enforce the exactly-one constraint via blockade.

Copy and crossing gadgets baseline — Composite copy and crossing gadgets: copy gadgets propagate a logical state along a 1D chain, and crossing gadgets allow logical wires to cross without unwanted coupling.

Optimised copy and crossing — Optimised version of the copy and crossing composite, showing reduced atom count via reordering and elimination of redundant dummies.

Diff between baseline and optimised composites — Side-by-side comparison of baseline and optimised composite structures, highlighting the atom-count saving achievable by the proposed reordering.

Cross-Copy composite example — An example composite structure realising a multi-constraint CSP via overlapping xor₁ gadgets, copy chains, and crossings — illustrates how arbitrary Boolean conjunctions are embedded planarly.

N-queens benchmark embedding: each row, column, and diagonal becomes an exactly-one constraint; the xor₁ encoding requires 54% fewer atoms than the QUBO embedding.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y2 (quasi-binary, hard mixer, no penalty): Both papers replace QUBO penalty terms with structured constraint-preserving mechanisms. Y2 does this at the algorithmic level via a hard-constraint mixer in the QAOA evolution; this paper does it at the hardware level via geometric blockade. The motivating observation — penalty terms inflate the dynamic range and degrade feasibility — is identical. The 99% detuning reduction here is the analogue of Y2's qubit-count reduction (~2 log₂(U−L+1) per variable).
Y4 (Grover + cardinality-constrained binary opt): Both treat the constrained subspace ("exactly k ones," "exactly one per group") as a first-class object, not via penalty enforcement. Y4 uses Grover with a Dicke-state preparation; this paper uses a Rydberg gadget. Different platforms, same spirit of designing for the feasible subspace.
Y3 (DGMVP portfolio, end-to-end QAOA): The gate-assignment / N-queens benchmarks are the same flavour of resource-constrained scheduling that motivates Y3's portfolio work, though Y3 lives in QAOA + IBM gate-model land rather than analog Rydberg.

Recommended action for Yuan

Read carefully and consider citing in any future Y2 follow-up: the xor₁ gadget is a hardware analogue of Y2's hard mixer. Direct comparison ("constraint preservation: at mixer level [Y2] versus hardware level [this work]") would strengthen the framing of Y2 as a general principle.
Run a head-to-head on a small portfolio instance: if a small DGMVP / cardinality-constrained portfolio instance from Y3 fits into ~30–50 atoms in the xor₁ encoding, compare achieved approximation ratio on a real Rydberg device against the QAOA results in Y3. This would directly probe whether Y2's qubit savings are equally beneficial in the analog Rydberg regime.
Email the authors: Panahiyan / Jaksch (Hamburg / Oxford) work on neutral-atom optimisation and may be open to a collaboration on financial cardinality-constrained instances — the gate-assignment formulation maps neatly onto portfolio cardinality.