Shots-to-Approximate-Solution Scaling in Neutral-Atom Quantum Optimization

AI summary

Overview

Research area: Quantum optimization benchmarking on neutral-atom (Rydberg) hardware, specifically the maximum independent set (MIS) problem and how the cost of sampling good solutions scales with the quality of solution demanded.

Technical level: Intermediate. The paper is written for readers who know what a Hamiltonian, a bitstring, and an approximation ratio are, but its central idea — a "shots-to-solution" cost curve — is explained with enough care to be followed by non-specialists.

Scope (one sentence): The paper introduces a shot-count metric, STS(r), plus a one-parameter "shell" model of postprocessed outputs and an excitation-matched random baseline, and applies them to Rydberg-atom annealing data on graphs with up to 125 sites to show that quantum advantage in shot cost depends strongly on how close to optimal the target solution must be.

What This Paper Is About

Neutral-atom arrays can encode the maximum independent set problem natively, but existing benchmarks mostly ask either "did we find the exact optimum?" or "what is the average quality of the samples?" — they do not answer the practical question of how many experimental shots are needed to reach a solution of a specified quality. This paper supplies that missing cost curve: it defines the number of shots required to obtain, with 99% confidence, at least one postprocessed output meeting a target approximation ratio r, and measures it on real hardware. The goal is to separate a genuine quantum effect (concentration toward near-optimal solution structure) from a trivial one (how many atoms happen to be excited per shot), and then to see how the resulting advantage depends on how demanding the target is.

Key Contributions

1. A shot-cost metric, STS(r; N). Defined as ⌈ln(1 − p_req)/ln(1 − p_r)⌉, the number of independent shots needed to hit approximation ratio r with confidence p_req (set to 0.99 throughout), where p_r is the per-shot success probability. This converts a distribution of solution qualities into an operational, device-level cost.

2. A one-parameter shell model of postprocessed outputs. Solutions are labelled by a shell index j = α − |S_post| (j = 0 is the MIS manifold), and the shell distribution is modelled as π_j(β) ∝ d_{α−j} e^{−βj}, a degeneracy-weighted Boltzmann-like form with a single parameter β. β is given both a maximum-entropy justification (it is the Lagrange multiplier conjugate to the mean shell depth) and an algorithmic derivation for finite-range postprocessing on short-range-correlated inputs, with corrections of order 𝒪(j²/N).

3. An excitation-matched random baseline. Because postprocessing acts on raw bitstrings, different Rydberg excitation densities alone can change the final shell distribution; the paper therefore applies the identical postprocessing to Bernoulli(p_exc) bitstrings matched to the measured mean excitation density, and reports the residual Δβ_ann = β_ann − β_rand(p_exc^(ann)) as the genuine concentration advantage.

4. An experimental demonstration and a two-regime scaling result. Using QuEra Aquila with 500 shots per instance across four size groups and up to 125 sites, the paper shows annealing consistently beats the matched baseline, and that the operational value of that advantage collapses for relaxed targets.

Main Findings

• Annealing beats the excitation-matched baseline. At the plateau (T = 5000 ns), Δβ_ann is positive in all four size groups, with group means of 0.40 ± 0.41 (small), 0.28 ± 0.25 (medium), 0.30 ± 0.20 (large), and 0.23 ± 0.14 (xlarge). At the instance level, Δβ_ann > 0 for 86 of the 96 instances in hardness bins 1–4 (90%; specifically 21/24, 20/24, 22/24, and 23/24 from small to xlarge).

• A saturation plateau in annealing time. Δβ_ann(T) rises from negative or near-zero values at short sweep times and approaches a positive plateau around T* ≈ 2500–5000 ns, depending on the size group.

• β is essentially size-independent. Group values of β_ann span 3.79–4.06, comparable to within-group scatter; a per-instance regression against N gives a slope of −5.7 × 10⁻⁴ per site (95% CI [−2.5, +1.4] × 10⁻³, p = 0.57). The paper explains this as expected, since β is a log-probability per defect and hence intensive, with the extensive growth of shot cost entering through the degeneracy factors d_{α−j} rather than through β.

• The apparent decay of Δβ_ann is carried by the smallest group. The nominal drop from 0.40 (small) to 0.23 (xlarge) gives an overall slope of −1.7 × 10⁻³ per site (95% CI [−3.3, −0.1] × 10⁻³, p = 0.04, R² = 0.05), but excluding the small group the slope is consistent with zero (−8.2 × 10⁻⁴, p = 0.40). The authors explicitly state they do not read Table 1 as evidence of systematic decay with system size.

• Two target-dependent regimes. For near-exact targets (r ≈ 1, i.e. J = 0), STS grows approximately exponentially with N, with fitted growth rates κ = 0.035–0.040 across the four groups — nearly indistinguishable, so the improvement from larger β appears chiefly as a prefactor reduction within the shell-model description rather than a resolvable change in slope. For a relaxed target (r = 0.9), the shot cost stays close to unity across the whole size range, and the excitation-matched random baselines also lie in that order-unity regime.

• Direct counting confirms the two-regime structure without the model. At the exact target, median counts in shells j ≤ J(r) are 146.5, 45, 12, and 5 per 500 shots (small to xlarge, bins 1–4), giving direct-count STS(r = 1) of 14, 49, 190, and 459, versus shell-model values of 11, 27, 63, and 140. The xlarge direct count rests on 5 exact hits in 500 shots and carries roughly 45% counting uncertainty. At the relaxed target, direct counting gives STS(r = 0.9) = 2 in every group.

• The shell model fits well but underestimates the cost of exact solutions. Over 97% of tested instances satisfy D_KL < 0.1 against the one-parameter fit. However, at J = 0 the model overestimates π_0 by up to a factor of about 3 (about 1.2 in the small group, growing to 2–3 in the larger groups), while for J ≥ 1 the direct counts and model agree within 25% in the large and xlarge groups. The authors therefore state that shell-model STS(r = 1) should be read as a lower bound at that level, attributing the gap to d_α counting all maximum independent sets rather than the 1-swap-stable ones the pipeline can return.

• The model passes a controlled sensitivity check. On mock data built by flipping each bit of the exact MIS solution with probability p ∈ {0.05, 0.1, …, 0.5} (2000 mock shots per instance), the inferred β decreases monotonically with p in all size groups and bins, dropping by roughly 3.5–4 across the decade p = 0.05–0.5, consistent with a mixture of single- and double-flip defect channels.

• A caveat the authors state plainly. The relaxed-target regime is one where the classical postprocessing heuristic alone reaches the target in order-unity attempts, and the paper notes that for the structured graph families used (geometric unit-disk and King's-lattice graphs) polynomial-time approximation schemes exist — so these instances are classically tractable, which is why the measured classical reference cost is reported alongside the quantum shot counts.

Methodology in Plain English

The problem setup. The team encodes maximum independent set instances as site-diluted induced subgraphs of a King's lattice, with lattice spacing a = 5.0 μm chosen to satisfy the blockade condition a < R_b < a√2, so that nearby excitations are energetically forbidden by the Rydberg blockade. All experiments ran on QuEra Aquila with M = 500 shots per instance.

The annealing schedule. The Rabi frequency is ramped from zero over T_ramp = 100 ns, then held at Ω = 2π × 1 MHz while the detuning is swept linearly from Δ_i/2π = −3.0 MHz to Δ_f/2π = +2.0 MHz over total evolution times T ∈ {500, 1000, 1500, 2000, 2500, 3000, 4000, 5000} ns.

The dataset. Four size groups — small (N = 30–35), medium (N = 60–65), large (N = 90–95), and xlarge (N = 120–125) — with 30 instances in each group. Mean exact MIS sizes ᾱ run from 12.2 to 43.9, which sets the granularity Δr ≃ 1/α of accessible target ratios. Within each group, instances are split into five hardness bins by the proxy H(G) = d_{α−1}/(α d_α), which measures near-optimal versus optimal degeneracy; the easiest bin (bin 0) is kept but excluded from averaged analyses because postprocessing there resolves the MIS with high probability and the shell distribution becomes qualitatively different.

The postprocessing pipeline. Raw bitstrings are rarely valid independent sets, so every shot goes through three deterministic stages: (i) feasibility projection, removing atoms involved in blockade violations; (ii) greedy maximization, adding atoms without violating constraints; (iii) ℓ-swap local improvement, accepting swaps that strictly increase set size. All analysis — fitting, baselining, shot counting — is done on these postprocessed sets, not raw bitstrings.

The baseline trick. To avoid crediting the quantum device for a trivial effect, the same pipeline is applied to Bernoulli(p_exc^(ann)) random bitstrings, using 500 samples to match the experimental shot count. The measured excitation density is p_exc^(ann) ≈ 0.26, well below the 0.5 of a uniform random baseline — the reason a naive comparison would conflate density with structure. The authors deliberately match only the one-point statistic: the number of blockade-violating edges is itself a signature of the physics under test, and a single Bernoulli parameter cannot satisfy two constraints anyway.

From β to shot counts. The fitted β, together with the shell cutoff J(r) = α − ⌈rα⌉, yields p_r = Σ_{j=0}^{J(r)} π_j, which is plugged into the STS formula. As a model-free cross-check, the fraction of the 500 shots landing in shells j ≤ J(r) gives a direct estimate of p_r at every admissible cutoff.

Why This Matters

Impact on research. Prior neutral-atom benchmarking largely reported exact-solution success or summary statistics of approximation quality. This paper reframes the question in terms of a device-level cost — physical shots — and shows that the answer depends qualitatively on the target ratio. It also supplies a null model that separates quantum structural correlations from excitation-density artifacts, a control that is easy to omit and that materially changes the interpretation of postprocessed results. The explicit statement that the shell-model exact-target shot cost is a lower bound, and the disclosure of the classical reference cost on classically tractable graph families, make the reported advantage unusually well-scoped.

Real-world applications. The paper itself does not enumerate applications; the following follow from the MIS problem class it studies rather than from claims made in the text.

• Network and infrastructure design: selecting non-conflicting facilities, towers, or links where adjacency constraints forbid simultaneous selection.
• Scheduling and resource allocation: choosing mutually compatible tasks, jobs, or time slots under conflict constraints.
• Logistics and packing: selecting non-overlapping items, routes, or container assignments.
• Wireless and sensor placement: choosing transmitting nodes or sensor sites that must not interfere with neighbours.

Industry relevance. The STS framing is directly useful to anyone evaluating whether a quantum device is worth integrating into a hybrid pipeline: it answers "how many shots per good answer" rather than "how good is the average sample," and it makes the answer commensurable with the classical postprocessing heuristic that runs alongside the device. The finding that relaxed targets cost order-unity shots even for the matched random baseline is a caution against headline claims of quantum advantage based on near-optimal-but-not-optimal solutions.

Future Directions

• Distinguishing effective temperature from defect density. The paper notes that β measures the density of postprocessing-irreparable defects, and that a genuine effective temperature would control that same density, making β a monotone proxy rather than a temperature. The shell distribution alone cannot settle this, because the same degeneracy-weighted form arises for any product-measure input, including the non-thermal Bernoulli baseline; the authors point to raw bitstring statistics as the required next step.

• A stable-set-count refinement of the degeneracy factor. The overestimate of π_0 by up to a factor of about 3 is attributed to d_α counting all maximum independent sets rather than the 1-swap-stable ones the pipeline can actually return. Correcting this is the natural route to a trustworthy (rather than lower-bound) exact-target shot cost.

• Testing the baseline choice. The authors expect an edge-matched product ensemble to shift β_rand only slightly at the present system sizes, and an edge-matched variant is noted to exist but to reproduce a substantially lower excitation density — a prediction that invites direct test.

• Extending the size range. Because the apparent decay of Δβ_ann with N is carried entirely by the small group and vanishes when that group is excluded, larger arrays would be needed to determine whether the structural advantage truly persists at scale or eventually erodes.

Target Audience

Experimentalists and theorists working on neutral-atom quantum optimization and quantum annealing benchmarking; researchers in hybrid quantum-classical algorithms who need device-level cost metrics rather than per-sample quality statistics; and industry or lab practitioners deciding whether a Rydberg platform's output justifies the shot budget for a given accuracy requirement. Readers focused on asymptotic quantum advantage should note the paper's own framing: the graph families studied are classically tractable, and the relaxed-target regime is one where the classical postprocessing heuristic alone succeeds in order-unity attempts.

Authors’ abstract

Whether neutral-atom quantum optimization protocols exhibit genuine concentration toward low-energy solution structure remains an open question. Here, we introduce a shots-to-approximate-solution metric, STS(r), where r denotes the approximation ratio, and evaluate it using postprocessed outputs modeled by a degeneracy-weighted shell distribution governed by a single effective parameter, $β$, that quantifies concentration toward near-optimal independent sets. To extract the genuine concentration effect in the quantum data, we apply identical postprocessing to both experimental bitstrings and randomly generated bitstrings with matched excitation density, thereby constructing an excitation-matched random baseline. Experiments on programmable Rydberg-atom arrays with system sizes up to 125 sites show that quantum annealing consistently exceeds the random baseline, demonstrating enhanced concentration toward low-energy solution structure beyond what can be attributed solely to excitation density. The results further reveal two distinct target-dependent regimes. For near-exact targets with $r \approx 1$, the required shot count grows exponentially with system size and is reduced at the same exponential level by quantum annealing within the shell-model description. By contrast, for relaxed targets, the shot cost becomes effectively constant, and the corresponding quantum enhancement diminishes, with the classical postprocessing heuristic alone reaching the target in order-unity attempts. Together, these results establish an operational method for quantifying quantum optimization performance and clarify the regimes under which quantum approaches can yield practical benefits.