Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
arXiv:2508.06130 · doi:10.1103/3sjz-gfmr
Abstract
Programmable quantum systems based on Rydberg atom arrays have recently emerged as a promising testbed 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-theoretic limits of polynomial reductions from arbitrary graphs to unit-disk 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-and-conquer heuristic with only linear overhead which leverages precalibrated atomic layouts. We benchmark it on Erdös-Rényi graphs, and demonstrate feasibility on the Orion Alpha processor.
13 pages, 4 figures
References in corpus (28)
- Quantum information with Rydberg atoms
- Ising formulations of many NP problems
- Many-Body Physics with Individually-Controlled Rydberg Atoms
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Observation of Rydberg blockade between two atoms
- Periodically-driven quantum systems: Effective Hamiltonians and engineered gauge fields
- Realizing quantum Ising models in tunable two-dimensional arrays of single Rydberg atoms
- Synthetic three-dimensional atomic structures assembled atom by atom
- Quantum computing with neutral atoms
- ARC: An open-source library for calculating properties of alkali Rydberg atoms
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Quantum simulation and computing with Rydberg-interacting qubits
- Single-atom trapping in holographic 2D arrays of microtraps with arbitrary geometries
- Direct measurement of the van der Waals interaction between two Rydberg atoms
- Microwave-engineering of programmable XXZ Hamiltonians in arrays of Rydberg atoms
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Digital-Analog Quantum Computation
- Quantum simulation of Ising spins on Platonic graphs
- Rydberg blockade based parity quantum optimization
- Parity Quantum Optimization: Compiler
- Quantum pricing-based column-generation framework for hard combinatorial problems
- Digital-Analog Quantum Computation with Arbitrary Two-Body Hamiltonians
- Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs
- Rydberg-atom graphs for quadratic unconstrained binary optimization problems
- Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
- Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor
- Universal quantum processors in spin systems via robust local pulse sequences
- Implementing transferable annealing protocols for combinatorial optimisation on neutral atom quantum processors: a case study on smart-charging of electric vehicles