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 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.
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 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.
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.
We present a hardware-native gadget framework for solving constraint satisfaction problems on Rydberg quantum computing architectures. Our approach introduces a compact xor1 gadget that enforces exactly-one constraints, ubiquitous in combinatorial optimization, directly through geometric embedding and blockade interactions. A key advantage of the xor1 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.
We introduce parity quantum optimization with the aim of solving optimization problems consisting of arbitrary k -body interactions and side conditions using planar quantum chip architectures. The method introduces a decomposition of the problem graph with arbitrary k -body terms using generalized closed cycles of a hypergraph. Side conditions of the optimization problem in form of hard constraints can be included as open cycles containing the terms involved in the side conditions. The generalized parity mapping thus circumvents the need to translate optimization problems to a quadratic unconstrained binary optimization problem (QUBO) and allows for the direct encoding of higher-order constrained binary optimization problems (HCBO) on a square lattice and full parallelizability of gates.