Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914264412848128 |
|---|---|
| author | Cazals, Pierre Sorondo, Amalia Onofre, Victor Dalyac, Constantin Coelho, Wesley da Silva Vitale, Vittorio |
| author_facet | Cazals, Pierre Sorondo, Amalia Onofre, Victor Dalyac, Constantin Coelho, Wesley da Silva Vitale, Vittorio |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06130 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach Cazals, Pierre Sorondo, Amalia Onofre, Victor Dalyac, Constantin Coelho, Wesley da Silva Vitale, Vittorio Quantum Physics 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. |
| title | Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2508.06130 |