arXiv:2610.28528
Efficient Ground-State Manifold Amplification for Rydberg Atom Arrays via Houdayer Cluster Updates
Andrew J. Ochoa, Martin J. A. Schuetz, Helmut G. Katzgraber
Abstract
We demonstrate a hybrid quantum-classical approach for exploring ground-state manifolds of maximum independent set problems, in which quantum hardware supplies the initial solutions and an entirely classical post-processing algorithm expands them, increasing the solution diversity of quantum hardware measurements by up to several orders of magnitude. Quantum optimization devices, while capable of generating high-quality solutions, can suffer from fundamental sampling limitations. This is particularly problematic for applications that strongly depend on a large variety of uncorrelated optimal solutions. We apply the Houdayer cluster update algorithm to systematically expand quantum-generated solution sets through classical post-processing. We validate our approach on a test bed of 43 problem instances from QuEra's Aquila analog annealing device, achieving diversity amplification factors, defined as the increase in the number of distinct solutions at a given set size, of up to 11923x with a median of 24.3x across different problem scales and hardness parameters. Because exact ground-state degeneracies are known for these instances, the recovered fraction of the manifold can be measured rather than bounded: post-processing recovers a median of 21% of the ground-state manifold, and provably all of it for six instances. We also demonstrate that, in some cases, the classical post-processing can discover independent sets larger than those found by the quantum hardware, thus improving on solution quality and not just diversity. While the method is non-ergodic and cannot guarantee complete manifold coverage, it consistently discovers a larger number of high-quality, and in some cases strictly better, configurations than quantum sampling alone. This work demonstrates how simple classical post-processing can enhance the utility of quantum optimization results.
AI Summary
The paper asks how many additional optimal configurations can be recovered from a fixed Rydberg-array optimization record using classical post-processing. It applies existing Houdayer cluster updates to maximum independent set (MIS) samples from QuEra’s Aquila device, studying 43 unit-disk graph instances with 7–231 atoms. After greedy repair of hardware measurements, each seed pair is decomposed into connected components of its symmetric difference. Independently exchanging the $c$ components generates $2^c$ independent sets. For two maximum independent sets, every component is balanced, so exchanges preserve optimal cardinality; suboptimal parents can yield larger sets. Each pass processes only pairs of its initial seeds, with exhaustive enumeration or saturation-based stopping. Distinct-configuration counts increase by a median $24.3\times$ overall and up to $11923\times$, reaching approximately 1.97 million configurations on one instance. For the 35 instances whose seeds already reach the exact optimum, median amplification is $8.9\times$ and median ground-state coverage is 21.4%, with complete coverage on six instances. Coverage is measured against exact degeneracies using reference data and transfer-matrix calculations. Processing the full dataset takes approximately 18 minutes on one laptop core. Eight seed pools are suboptimal; post-processing improves three, reaching the optimum on one and remaining one vertex short on two. The method is non-ergodic, and coverage falls as degeneracy grows. Distinct counts do not establish uniform or uncorrelated sampling. Local search gives comparable counts on many instances and matches two quality improvements. No classical-seed control isolates the quantum seeds’ contribution; performance is tested only on these geometrically structured graphs.
Error found: The abstract leaves unstated that its median 21% ground-state-manifold coverage is calculated only over the 35 instances with initially optimal seeds, rather than the full 43-instance test bed.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 15 pages, 6 figures, 1 table. v2: corrects three numerical values in Secs. III A, III E and V. Results unchanged