Quantum samplers fail to fill the classical repair basin: tabu search leads at 0.82–0.94 basin mass in a preregistered test
Synopsis
After porting the quantum-chemistry pipeline of a generative model writing circuits, a quantum sampler drawing bitstrings, classical repair expanding them and a classical solver picking the best, to maximum weighted independent set, a preregistered held-out test returns a negative answer: tabu search reaches repair-basin mass 0.82–0.94 and simulated annealing comes second, while every quantum sampler and a matched learned classical policy trails both at every size. An earlier positive-looking result came from picking the best of 50 configurations per instance, an upper bound rather than a deployable method; under random configurations, oracle QAOA reaches only 0.014 at n=28.
Interpretation
Whether a quantum sampler can place more probability mass inside a classical repair basin is now a directly comparable quantity: the probability that the sampler's distribution lands on states from which repair plus r flips reaches an optimum. The usual measure for such hybrid pipelines was the fraction of the solution space covered by the sampled subspace, which under a fixed 200-shot budget is about 200 divided by 2 to the n and necessarily shrinks toward zero as size grows. On maximum weighted independent set, all 150 benchmark optima were certified with the CBC solver plus brute-force enumeration, and for instances with n at most 20 the repair-basin masks were enumerated exactly, so the probability is computed rather than estimated.
On the frozen held-out test set, strong classical samplers won the comparison, and the quantum samplers showed no structural advantage. Tabu search reached basin mass 0.82–0.94 across n=16 to 28 and simulated annealing 0.088–0.428, while uniform, greedy, multi-start local search, Metropolis, warm-start QAOA and oracle QAOA all scored lower. Nine samplers each received 200 shots per graph under the same repair and 2-flip expansion, and in paired per-instance comparisons oracle QAOA won zero of six instances against simulated annealing at n=16, 20 and 28.
A graph-conditioned classical policy with about 140K parameters lands at the same level as oracle QAOA, indicating that the quantum circuit's proposal distribution can be reproduced by a classical model of comparable size. That policy's basin mass spans 0.005–0.101 against oracle QAOA's 0.014–0.113, and the two ranges overlap. The comparison uses the same held-out test set, the same sampling budget and the same repair pipeline, with train, validation and test split by seeds 42–59, 60–65 and 66–71.
On the 20-qubit trapped-ion Piast-Q processor, all 136 frozen circuits completed, and QPU samples after classical repair matched simulator samples at a 93.4% optimal hit rate. Raw QPU samples hit the optimum 34 of 136 times versus 18 of 136 for the simulator, yet both converged to 127 of 136 after repair. The run covered maximum weighted independent set, balanced partition and MaxCut at sizes n=8 to 20, totaling 32,000 shots with no failed circuits.
Perspective
The conclusion covers maximum weighted independent set at n=16 to 28 on a held-out test set, with a fixed budget of 200 shots per graph, repair by 2-flip neighborhood expansion, and the quantum side limited to shallow QAOA-derived proposal distributions. The hardware portion tests portability only: all 136 frozen circuits completed on Piast-Q, and QPU and simulator samples both reached 127 of 136 after repair, which shows the repair pipeline still works under hardware noise rather than that quantum sampling improves optimization. At larger scale, classical repair first fails near n=55 and fails completely at n=80, a region flagged as where sampler quality may matter but not yet compared across the nine samplers.
The authors explicitly claim no quantum advantage and attribute the earlier positive n=28 result of 0.185 versus 0.130 to per-instance selection among 50 configurations, an upper bound rather than a deployable method. The learned policy's mean basin mass at n=28, 0.130, slightly exceeds simulated annealing's 0.115, but its median of 0.045 is far below 0.108, the mean being lifted by a few high instances, and it wins only 11 of 30 instances. The observation that noise raised sample diversity by 2–7% comes from a single n=10 instance and is called preliminary, with an irregular relationship among noise level, diversity and solution quality. The generative policy was trained for only 100 episodes in the easy regime where recovery always succeeds, and has not been validated where sampler quality actually changes the outcome.