Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers

Quantum Physics [Submitted on 30 Mar 2026] Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers Cédrick Perron, Yves Bérubé-Lauzière, Victor Drouin-Touchette Neutral atom quantum computers (NAQCs) have emerged as a promising platform for solving the maximum weighted independent set (MWIS) problem. However, analog quantum approaches face two key limitations: constraints of the atomic layout on realizable graph geometries and the absence of performance guarantees. We introduce Lp-Quts, a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm. At each iteration, a relaxed linear program (RLP) bounds the MWIS and induces a reduced graph from which independent sets are sampled using an analog quantum sampler. A novel sample-informed separation problem guides odd-cycle cut selection and accelerates convergence. For t-perfect graphs, Lp-Quts inherits polynomial-time convergence guarantees from the classical theory of cutting planes. We evaluate our approach on instances with up to 300 vertices -- a scale that exceeds the capabilities of current NAQC hardware. In this regime, Lp-Quts reaches solutions within 5--10\% of optimality, outperforming direct analog quantum protocols and greedy baselines under equal sampling budgets. As expected, simulated annealing remains the strongest sample-based solver at this scale. These results demonstrate how quantum samplers can be effectively embedded within classical optimization frameworks to deliver near-optimal solutions with reduced quantum resources while preserving formal guarantees. Subjects: Quantum Physics (quant-ph) Cite as: arXiv:2603.28933 [quant-ph]   (or arXiv:2603.28933v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2603.28933 Focus to learn more Submission history From: Cedrick Perron Mr [view email] [v1] Mon, 30 Mar 2026 19:12:21 UTC (1,546 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-03 References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)