A slack-free QUBO encoding with a feasibility guarantee, and two measured rules

A constrained problem goes to a quantum optimizer as a QUBO, a cost function over yes/no variables. The usual encoding spends extra qubits, called slack variables, tracking the battery's level at every hour. Mine drops them and checks the level every k hours instead, which bounds how far the level can drift between checks. That gives a property I can prove, soundness, which says that whenever the spacing passes a condition the code computes, every assignment that scores zero penalty is a schedule the battery can physically run. An assignment is any way of setting the yes/no variables, so this is a promise about all of them. On the real instance the encoding takes 117 qubits to 52 and loses none of the answer's value.

The qubit count is not the claim, and neither is removing slack variables. That is a crowded field: unbalanced penalization, exponential and Heaviside penalties, Lagrangian and augmented-Lagrangian methods, and, in this exact application area, a Powell–Hestenes–Rockafellar formulation. The nearest published work, a 2022 unit-commitment circuit by Halffmann and colleagues, removes slack variables for the same reason I do and reached the qubit saving first. What remains mine, the guarantee, is narrower. Their protection is about the winner, in that an infeasible plan must not score best, which rests on a penalty weight being set large enough. Mine is about the whole zero-penalty set, in that every plan that scores a perfect zero is one the battery can run, proved at any weight, for a battery level that accumulates across the whole day. A 2026 survey of quantum methods for unit commitment, the power industry's version of this scheduling problem, records no encoding with that property.

That claim rests on my not finding something, which is weaker evidence than finding it. It has already been narrowed once, because the two nearest constructions above came from the survey's reference list, read after my first search, and when I read them the slack removal and the qubit saving came off the list of what I call new.

I also measured what the guarantee is worth. Below the sound range the QUBO's own best-scoring state is not a schedule, which the usual success number cannot tell. At one weak setting, 32 of 40 tunings clear the five-times-guessing bar, although every one of them is probability piled on a state that is not an answer. Three tests hold the claim up. The first enumerates every zero-penalty assignment on three instances and finds all of them feasible. The second checks the best-scoring assignment at sizes past brute force. And the third confirms the encoding refuses to build at an unsound spacing, rather than silently biasing.

Tuning from many random starts leaves a pile of candidates, of which the standard rule keeps the one with the lowest energy estimate, the circuit's own score. Keeping the one that puts the most probability on feasible schedules picks a better circuit. The share of feasible samples has a published name, in-constraint probability. A cell is one version of the problem at one penalty weight. In every sound, repeatable cell I tested, the feasible-share rule picked the single best tuning available: 9 of 9 on instances held out of the rule's discovery, 12 of 12 on three fresh instances, 4 of 4 sizes from 8 to 14 qubits. On the two hard instances, where the best tuning barely clears the bar, the energy rule misses in every cell and this rule clears in every cell. The literature already uses in-constraint probability as a constraint inside the optimizer. The head-to-head among finished tunings is the only part a day's search did not find, although it is a small step from what is published.

The limits. Only two of six instances are hard enough to separate the rules. The median margin is 5.0%, which matters only when the best tuning sits at the bar. The largest size I tested can still be checked exactly, so the size result shows what a limited sample does, not what an impossibly large problem does. And where samples are cheap there is a better rule still, selecting on how often the best plan itself shows up. That one stops working at 14 qubits, where the best plan appears at all in only 7 of 20 tunings at 4,096 samples.