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.
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.
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.
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.
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% across different layout geometries. Experimentally, on the QuEra Aquila QPU, the Cluster decoder recovers exact optimization solutions with an average success rate of ≳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.
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.
Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.
We provide a non-unit-disk framework to solve combinatorial optimization problems such as maximum cut and maximum independent set on a Rydberg quantum annealer. Our setup consists of a many-body interacting Rydberg system where locally controllable light shifts are applied to individual qubits in order to map the graph problem onto the Ising spin model. Exploiting the flexibility that optical tweezers offer in terms of spatial arrangement, our numerical simulations implement the local-detuning protocol while globally driving the Rydberg annealer to the desired many-body ground state, which is also the solution to the optimization problem. Using optimal control methods, these solutions are obtained for prototype graphs with varying sizes at timescales well within the system lifetime and with approximation ratios close to one. The nonblockade approach facilitates the encoding of graph problems with specific topologies that can be realized in two-dimensional Rydberg configurations and is applicable to both unweighted as well as weighted graphs. A comparative analysis with fast simulated annealing is provided which highlights the advantages of our scheme in terms of system size, hardness of the graph, and the number of iterations required to converge to the solution. Published by the American Physical Society 2024