A Backend-Agnostic MWIS Kernel for Stochastic Unit Commitment with Neutral-Atom Hardware Validation

AI summary

Overview

Research area: Quantum computing for energy systems optimisation — specifically neutral-atom (Rydberg) quantum hardware applied to stochastic unit commitment (UC), with a green-hydrogen electrolyser park as the industrial test case.

Technical level: Advanced. The paper assumes familiarity with mixed-integer programming, LP duality, maximum-weight independent set (MWIS) formulations, and Rydberg analog Hamiltonian simulation (AHS).

Scope (one sentence): The paper defines a solver-agnostic compilation of stochastic UC into a move-based MWIS conflict graph, keeps dispatch and feasibility recovery classical, and validates the full loop end-to-end on the QuEra Aquila neutral-atom processor over a 15-day campaign at 50 nodes plus a single-day scaling sweep to 144 nodes.

What This Paper Is About

Stochastic unit commitment decides, for each of N controllable units over a T-hour horizon, which units to switch on and at what operating point, so that a delivery contract is met under uncertain supply at minimum cost. The on/off layer is combinatorial while the dispatch layer is a continuous program; for N = 6 and T = 24 the naive binary space is 2^(N×T) ≈ 2.2 × 10^43 configurations, most infeasible under production and inventory constraints.

The paper's goal is to remove two practical blockers: mapping a real operational model onto a hardware-compatible instance, and converting noisy hardware output back into a feasible decision. It does this by compiling only the discrete decision layer of stochastic UC into a maximum-weight independent set problem while retaining continuous dispatch and feasibility recovery in the classical layer, then running the graph-solving step on QuEra Aquila. The authors describe this as the first end-to-end industrial scheduling workflow connecting real operational decisions to programmable neutral-atom hardware through a solver-agnostic MWIS representation.

Key Contributions

1. A move-based MWIS compilation of stochastic UC. From a single feasible reference commitment, the kernel builds a vocabulary of six locally valid schedule perturbations (single-slot de-commit, contiguous 4-hour block de-commit, cross-module pair swap, k-module exchange, delete/insert, and clustered-integer neighbourhood adjustment). Each move is scored by LP duals from one 100-scenario stochastic LP solve, pruned to the top k = 50 with a diversity filter, and encoded as a weighted conflict graph where an edge joins moves touching a shared (module, hour) slot.

2. A zero-ancilla 2-row folding embedding. A flat 8-neighbour layout of the 24-hour, 6-module lattice requires 120 μm in x at s = 5 μm spacing, exceeding Aquila's 75 μm field of view. The folding splits the time axis at the point minimising the larger per-row occupied hour-span (exhaustive search, Eq. 4), uses per-row x-normalisation, and compresses x from 120 μm to 55 μm with y at 64 μm — both inside the 75 × 76 μm FOV, with no gadget overhead.

3. A hardware-validated AHS schedule recipe ("narrow-zero-cross"). An exhaustive 11-strategy sweep at N = 12 (a 2-row folded subgraph with 26 edges, weights in [−52.1, 101.9]), evaluated by exact dense diagonalisation over 2^12 = 4096 states at freeze time t = 0.9T, identified exactly one viable parameter family: Ω_max = 8 MHz, Δ_start = −30 MHz, Δ_end = +30 MHz, Δ_local_peak = −125 MHz (hardware maximum), T = 4 μs, plateau shape. Only 3 of 11 strategies pass the encoding gate, and all three share these critical parameters.

4. A closed end-to-end loop with dispatch repair validated on hardware. The pipeline runs UC → MWIS → Aquila → 100-scenario LP repair as a closed loop, with a 4-phase post-processing stage (broken-edge resolution, full King-graph independent-set enforcement, negative-weight pruning, greedy positive-weight-descending maximality augmentation) and a common simulated-annealing refinement stage on the true dispatch margin rather than the MWIS proxy — a capability absent from prior Aquila power-system work.

Main Findings

• Fifteen-day hardware campaign succeeds on every day. One 50-node, 200-shot AHS task per day was submitted over 15 consecutive days (126–153 edges), with all 15 scheduled days completing successfully. The post-processed AHS objective retained a mean 94.0% of the exact MWIS objective (median 0.975, minimum 0.748 on Day 2, maximum 1.000), clearing the paper's 0.60 viability threshold on all 15 days.

• End-to-end dispatch margins match or exceed exact MWIS on every day. After classical refinement and 100-scenario LP repair, hardware-generated solutions match or exceed the dispatch margins obtained from exact MWIS on every campaign day — the headline end-to-end claim, distinct from the inner-kernel objective ratio, which is at or below the exact optimum.

• Raw hardware output is noisy but contains the target bitstring. Raw AHS objective ratios span −1.519 to 0.857 (mean 0.113), with six days (Days 3, 4, 7, 8, 11, 13) producing negative raw objectives from surviving negative-weight noise atoms. The negative-weight-pruning phase, which is lossless by construction because no negative-weight node can belong to a true maximum-weight independent set, resolves all six to ratios of 0.808–1.000.

• The weakest post-processed day is not the worst hardware day. Day 2 has the lowest AHS-post ratio (0.748). Day 7 has both the lowest valid-shot rate (0.545) and the most discarded shots (91 of 200, 45.5%), yet still recovers to 0.808.

• The LP-dual proxy landscape is sharp. Exact MWIS via HiGHS MILP on a 50-candidate, 283-edge conflict graph reached a dual-proxy objective of 12.15 versus 3.63 for cold-start simulated annealing. A warm-started SA run seeded from the HiGHS solution converged to the same 12.15 at iteration 0, meaning the exact solution is already a local optimum under SA's neighbourhood and a cold start cannot reach it.

• Dual scoring beats the naive price proxy. The LP-dual move score is a first-order estimate of the move's effect on the LP objective; the paper reports that a naive electricity-price proxy failed in earlier experiments with 35% sign agreement with the ground-truth margin direction.

• Single-day rolling-horizon dispatch is feasible. Propagating each day's tank and battery terminal state forward as the next day's initial condition was feasible for a single day, with a positive LP margin of £23,622, 100% dispatch rate, and hydrogen balance residual at machine precision (~4.5 × 10^-13).

• Encoding quality is capped at rank 3, not rank 1. At N = 12 the best-achieved rank of the MWIS bitstring across the full sweep is 3 of 4096, with a gap of ≈1.7 MHz. The true ground state has one independent-set violation (bitstring rgrrgggggggg, value 214.76 vs MWIS 208.18). The usable encoding window is narrow: the target enters the bottom-10 at t/T = 0.85 and has collapsed by t/T = 0.95, a span of roughly 0.05T ≈ 200 ns at T = 4 μs.

• Schedule failures are diagnostic. Weak local detuning (−80 MHz, the old pipeline default) fails across all global sweep configurations (ranks 49–81); an all-negative global sweep (−90 → −70 MHz) suppresses all atoms indiscriminately (rank 68); zero global sweep fails even at hardware-maximum local detuning (ranks 31–35); the triangle shape compounds failure (rank 81 vs. rank 57 with plateau at the same detuning values). Evolution time is invariant within this recipe — ranks and gaps are identical at T = 2, 4, and 6 μs — because encoding depends on the ratio t/T.

• The old default schedule froze after collapse. The previous pipeline's default parameter set had rank-1 encoding at t/T = 0.7, but the freeze occurred at t/T = 0.9, which is 0.15T after the encoding had collapsed to rank 57.

• AHS post-processing beats a greedy heuristic. The greedy baseline matches or nearly matches exact MWIS on the two highest-mean-weight days (Day 1 exactly; Day 2 at 92.6%) but produces negative objectives on days with predominantly negative node weights (Days 4, 10, 11). AHS post-processing outperforms greedy on 13 of 15 days. Because phase 4 uses the same greedy rule as the baseline, the comparison isolates the value added by the AHS-selected seed set.

• Valid-shot rate, not graph embedding, limits scaling. On the single-day sweep at N = 75/100/125/144, encoding quality remains stable while the probability that the full atom array survives emerges as the dominant bottleneck — not the FOV occupancy or the graph embedding. This reflects Aquila's static traps filling with ~60% probability, which forces post-selection on fully loaded arrays.

• Broken-edge repair costs little. The 2-row folding severs Chebyshev-adjacent edges that cross rows; Ebadi-style greedy vertex reduction repairs them. Across the 15-day campaign the post-processed AHS selection retains a mean 94.0% of the exact MWIS objective (range 74.8–100%).

Methodology in Plain English

The authors separate the problem into a hard discrete piece and a continuous piece that classical solvers handle well, then send only the discrete piece to quantum hardware.

Build a starting schedule. They construct one feasible baseline commitment for a six-module, 24-hour green-hydrogen electrolyser park, for example by chronological fill (committing all modules hour by hour) or cheapest fill (prioritising the lowest-price module-hour slots).

Describe small edits instead of whole schedules. Rather than searching over all on/off patterns, they enumerate a vocabulary of local perturbations of that baseline — turn one slot off, turn a 4-hour block off, swap capacity between modules, exchange k modules, delete and insert, or adjust a cluster of integers. Each edit is a set of slots to switch off plus a set to switch on.

Score each edit with shadow prices. They solve the 100-scenario stochastic dispatch LP once with commitments fixed, using HiGHS, and read off the dual values of the power-balance and hydrogen-tank-dynamics constraints. These probability-weighted, sign-flipped marginals are combined with the electrolyser power (5.0 MW per module) and hydrogen yield (18.5 kg/MWh) into a single linear score per move. Scoring is therefore a handful of floating-point operations per candidate with no per-move re-optimisation; a separate development check re-solved the full LP once per move to validate the approximation, but that check is not part of the reported pipeline.

Turn edits into a graph. Keep the top 50 by absolute score subject to a diversity filter that limits how many moves may target any single slot, then connect two moves with an edge if they touch a shared (module, hour) cell. Selecting the best compatible set of edits is now a maximum-weight independent set problem, with the LP-dual scores as node weights.

Solve the graph, exactly or on hardware. Classically they solve it to optimality with the HiGHS MILP solver. On hardware, the same nodes are placed on a King-graph unit-disk layout, where Rydberg blockade physically enforces the independent-set constraint: two atoms within the blockade radius cannot both be excited. Node weights are encoded through per-site local detuning, with the normalised weight h_k interpolating each atom's effective detuning between a global sweep and a per-site offset — the same mechanism used in recent weighted Rydberg MWIS work. Because Aquila's local detuning is suppression-only, it can push an atom toward the ground state but never actively promote one, which is why weight bias is probabilistic rather than a hard constraint.

Fold the layout to fit. A 24-hour horizon at 5 μm spacing needs 120 μm, more than the 75 μm FOV allows. Splitting the hours into two stacked rows at the span-minimising split point, and normalising each row's x-origin independently, compresses the layout to 35 × 64 μm on Day 1 — well under half the available FOV. The fold breaks a small number of inter-row edges, which are repaired classically.

Tune the quantum pulse. They sweep 11 schedule strategies at N = 12, using exact diagonalisation to rank the MWIS bitstring's Ising energy against all 4096 possible bitstrings at each instant, as if the system were frozen and measured then. This classical diagnostic fixes the freeze time before any hardware submission, since exact diagonalisation is intractable at the deployed scale. The winning recipe sweeps global detuning from −30 to +30 MHz across the full duration while local detuning ramps to −125 MHz, holds, then retracts; the freeze at t/T = 0.9 captures the weight separation before the retraction erases it.

Refine and validate. The selected moves — from HiGHS or from post-processed AHS — seed a simulated annealing run over the same conflict graph, which refines but does not replace the graph solver. A dispatch step applies the moves and resolves any slot targeted by both an OFF and an ON move. Finally, a 100-scenario stochastic LP repair verifies delivery-contract feasibility and computes the realised margin, including grid-capacity and tank-dynamics constraints the geometric graph does not encode. This repair is a read-only gold standard: its output is never consulted during move generation or MWIS selection.

Why This Matters

Impact on research. The paper closes a loop that prior neutral-atom power-system work left open. The nearest comparable Aquila result is MaxCut on an IEEE 9-bus maximum-power-section task with up to 12 vertices and no unit-commitment or dispatch-repair layer; prior quantum UC work used QUBO-plus-LP splits on D-Wave annealers. This work demonstrates that a noisy, approximate hardware sample — one that on its own yields negative objectives on 6 of 15 days — can be post-processed into a feasible, competitive operational decision. It also frames the graph as a shared intermediate representation: the same conflict graph can be handed to AHS, converted to a QUBO for a quantum annealer, or mapped to an Ising Hamiltonian for

Authors’ abstract

Quantum hardware is beginning to address structured combinatorial optimisation, but two steps still block practical use: mapping real operational models onto hardware-compatible instances, and converting noisy hardware output back into feasible decisions. Here we introduce a backend-agnostic computational interface that compiles the discrete decision layer of stochastic unit commitment into a move-based maximum-weight independent set (MWIS) problem, while retaining continuous dispatch and feasibility recovery in the classical computational layer. We validate the approach in a green hydrogen scheduling setting and deploy it on the QuEra Aquila neutral-atom quantum processor. This is the first end-to-end industrial scheduling workflow that connects real operational decisions to programmable neutral-atom hardware through a solver-agnostic MWIS representation. Across a 15-day hardware campaign on 50-node instances, hardware-generated solutions after classical refinement match or exceed the dispatch margins obtained from exact MWIS on every day. When scaling to 144 nodes, encoding quality remains stable, while the probability that the full atom array survives, rather than graph embedding, emerges as the dominant bottleneck to further scaling. Together, these results establish a hardware-compatible computational pathway toward larger problem scales, and lay the groundwork for exploring regimes in which exact classical optimisation may no longer scale efficiently.