Reducibility of native weighted graphs on Rydberg Arrays
Abstract
We investigate the classical reducibility of random unit-disk graph (UDG) instances of the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems, which can be natively realised in Rydberg atom quantum processors. Using state-of-the-art kernelisation techniques, we systematically probe how far classical preprocessing can simplify such native optimisation problems of varying size and connectivity. While many small or sparse instances can be fully reduced, dense graphs often retain finite irreducible kernels even after extensive reductions. Introducing vertex weights tends to increase reducibility, whereas extending the interaction range in the underlying UDG connectivity suppresses the reduction efficiency. By exploring where classical reductions cease to be effective, we aim to delineate the regime of problem instances that remain computationally demanding - those most relevant for testing and benchmarking near-term quantum optimisation hardware. We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads, suggesting that directly running native instances may be more practical than embedding a reduced kernel.
Related
- Qudit encoding in Rydberg-blockaded arrays of atoms
- Practical roadmap to measurement-altered criticality in Rydberg arrays
- Meson spectroscopy of exotic symmetries of Ising criticality in Rydberg atom arrays
- Meson Spectroscopy of Exotic Symmetries of Ising Criticality in Rydberg Atom Arrays
- Exploring ground state phase diagrams of Rydberg atom arrays with finite projected entangled-pair states
BibTeX
@misc{kombe2026reducibility,
title = {{Reducibility of native weighted graphs on Rydberg Arrays}},
author = {J. Kombe and J. D. Pritchard},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.07952},
eprint = {2605.07952},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.07952},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Reducibility of native weighted graphs on Rydberg Arrays
AU - J. Kombe
AU - J. D. Pritchard
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2605.07952
UR - https://arxiv.org/abs/2605.07952
AB - We investigate the classical reducibility of random unit-disk graph (UDG) instances of the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems, which can be natively realised in Rydberg atom quantum processors. Using state-of-the-art kernelisation techniques, we systematically probe how far classical preprocessing can simplify such native optimisation problems of varying size and connectivity. While many small or sparse instances can be fully reduced, dense graphs often retain finite irreducible kernels even after extensive reductions. Introducing vertex weights tends to increase reducibility, whereas extending the interaction range in the underlying UDG connectivity suppresses the reduction efficiency. By exploring where classical reductions cease to be effective, we aim to delineate the regime of problem instances that remain computationally demanding - those most relevant for testing and benchmarking near-term quantum optimisation hardware. We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads, suggesting that directly running native instances may be more practical than embedding a reduced kernel.
ER -