Abstract There is a growing interest in harnessing the potential of the Rydberg‐atom system to address complex combinatorial optimization challenges. Here an experimental demonstration of how the quadratic unconstrained binary optimization (QUBO) problem can be effectively addressed using Rydberg‐atom graphs is presented. The Rydberg‐atom graphs are configurations of neutral atoms organized into mathematical graphs, facilitated by programmable optical tweezers, and designed to exhibit many‐body ground states that correspond to the maximum independent set (MIS) of their respective graphs. Four elementary Rydberg‐atom subgraph components are developed, not only to eliminate the need of local control but also to be robust against interatomic distance errors, while serving as the building blocks sufficient for formulating generic QUBO graphs. To validate the feasibility of the approach, a series of Rydberg‐atom experiments selected to demonstrate proof‐of‐concept operations of these building blocks are conducted. These experiments illustrate how these components can be used to programmatically encode the QUBO problems to Rydberg‐atom graphs and, by measuring their many‐body ground states, how their QUBO solutions are determined subsequently.
Abstract There is a growing interest in harnessing the potential of the Rydberg‐atom system to address complex combinatorial optimization challenges. Here an experimental demonstration of how the quadratic unconstrained binary optimization (QUBO) problem can be effectively addressed using Rydberg‐atom graphs is presented. The Rydberg‐atom graphs are configurations of neutral atoms organized into mathematical graphs, facilitated by programmable optical tweezers, and designed to exhibit many‐body ground states that correspond to the maximum independent set (MIS) of their respective graphs. Four elementary Rydberg‐atom subgraph components are developed, not only to eliminate the need of local control but also to be robust against interatomic distance errors, while serving as the building blocks sufficient for formulating generic QUBO graphs. To validate the feasibility of the approach, a series of Rydberg‐atom experiments selected to demonstrate proof‐of‐concept operations of these building blocks are conducted. These experiments illustrate how these components can be used to programmatically encode the QUBO problems to Rydberg‐atom graphs and, by measuring their many‐body ground states, how their QUBO solutions are determined subsequently.
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.
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 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.
Quantum computers relying on cold atoms are being built and promise a high flexibility in the way information in encoded into the physical system. In particular, the analog mode is spiking interest in the field of optimization as a classically intractable number of configurations can be tackled. In this work, we investigate a problem that requires every-day scheduling of critical tasks involving a large number of actors. Namely, fixing the planning for a Earth Observation satellite fleet composed of several of units exposed to a high density of targets to be scanned. We explore numerical schemes that convert the formulated problem into a cold-atoms friendly setup. We begin by a naive formulation of the Satellite Mission Planning problem without taking account for the agility of the satellites. We then extend the problem to take it into account based on the literature. By formulating the planning problem as a Maximum Independent Set problem, we are able to solve the problem with a QPU based on Rydberg atoms. We explore two ways of solving the MIS problem on the QPU, one relying on the graphs and on the Quadratic Unconstrained Binary Optimization Framework (QUBO). We show that the QUBO methodology is the most relevant and explore it more deeply with numerical experiments. We conclude on the potential utility of using a QPU to solve the Satellite Mission Planning problem in an operational context.
Programmable quantum systems utilizing Rydberg atoms have recently been shown to efficiently encode combinatorial optimization problems. The relationships among the variables in these optimization problems can be transformed into a maximum weighted independent set problem within the Rydberg atom system, requiring at most a quadratic overhead in terms of the number of qubits. Although experiments with current Rydberg quantum systems have demonstrated linear speedup compared to classical algorithms, the overhead in both the number of qubits and time remains substantial. To further reduce the overhead of encoding these optimization problems in Rydberg atom systems, we propose a simplification strategy and design a new heuristic algorithm that incorporates a topological sort approach to optimize the encoding process. We conduct extensive experiments on small graphs with dozens of qubits. The numerical results demonstrate the effectiveness of our algorithm in both runtime and optimization efficiency. Specifically, our algorithm reduces the number of required encoding qubits by 12.0% compared to existing methods. Additionally, our approach reduces the time complexity to a quadratic overhead, enabling experiments on larger graphs. The results further indicate that our algorithm provides significant time advantages over existing solutions.
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.