Scheduling and allocation

The largest set of tasks with no two in conflict

Transmitters that interfere at close range. Delivery slots that must not overlap. The most compatible jobs that fit one shift. All of them are one problem, maximum independent set, and it is NP-hard in general: choose as many items as possible with no two of them in conflict.

On gate hardware this is normally rewritten as a QUBO, a quadratic unconstrained binary optimisation in which every constraint becomes an energy penalty, and then attacked with QAOA. Neutral atoms do not work that way, and that is the reason this page exists.

The run below, on the job page. Open the console

The short version

The Rydberg blockade IS the constraint. Two atoms inside the radius cannot both be excited, which is the independent-set rule itself
No QUBO and no penalty weights. There is nothing to encode and nothing to tune, so a shot cannot violate the constraint by being badly weighted
Measured on QuEra Aquila: the optimum, from 9 atoms at 1,000 shots. 93.2% of shots came back a valid independent set and 60.6% were optimal
The geometry is the input, not the graph. Edges exist where atoms fall inside the blockade radius, so the family that maps directly is the unit-disk graphs

Run on our engines

Nine atoms on a 3x3 grid at 6 um spacing, whose blockade graph is the king's graph: 9 vertices, 20 edges, and a maximum independent set of 4 that can be checked by hand. Submitted to each kind of compute we offer, on 18 September 2026. Every figure below is a real job on the service, priced as any customer would be priced.

Engine	Kind	Qubits	Result	Cost
analog.pulser.cpu	CPU	9	found [0, 2, 6, 8], size 4; 500 of 500 shots valid	$0.0001
qpu.quera.aquila	QPU	9	found [0, 2, 6, 8], size 4; 883 of 947 shots valid, 574 optimalbest outcome	$10.3000
qpu.pasqal.fresnel	QPU	—	takes the identical Pulser sequence, but is billed as machine time at one shot per four seconds, so a run at this shot count is not comparable in cost	—

Both rows ran the identical register and both returned the same answer, the four corners. What differs is the share of shots that obeyed the constraint: every shot on the exact emulator, and 883 of the 947 Aquila returned. That gap is the blockade being imperfect on a real device, and it is the number to read first.

The same problem is yours to run: every instance here is seeded, so it rebuilds exactly. Open the console and a cost estimate is free before anything executes.

How the machine encodes it

Each item becomes an atom, and two atoms are connected when they sit within the blockade radius of each other. The sweep then does the work: start every atom in the ground state with the laser detuned well below resonance, ramp the drive on and sweep the detuning upward so excitation becomes favourable, and the blockade forbids neighbours from both being excited. What survives is an independent set. Ramp the drive off and measure; the excited atoms are the chosen items.

There is no penalty weight to tune and no constraint to check afterwards, because the physics could not violate it in the first place. The sweep is adiabatic in intent rather than in guarantee, which is where the caveats start, and they are below.

The instance, and why its answer is checkable

Nine atoms on a 3×3 grid at 6 um. At that spacing the orthogonal neighbours sit inside the 10.03 um blockade and so do the diagonals at 8.49 um, so the graph is the king’s graph on a 3×3 board: 9 vertices and 20 edges. The four corners are 12 um apart, outside the blockade, and no independent set of five exists, so the maximum independent set is 4 and a reader can verify that without running anything.

Each shot is one candidate set: an atom measured in the Rydberg state is an item chosen. Every shot is checked against the edge list, and shots that violate an edge are excluded from the answer and counted separately rather than quietly dropped.

Set size returned	Shots	Share of valid shots
4, the optimum	574	65.0%
3	235	26.6%
2	58	6.6%
1	16	1.8%

883 valid shots of the 947 Aquila returned. The remaining 64 violated an edge and are excluded.

Where this stops

The graph is not an input. You give positions and the edges follow from the geometry, so the family that maps with no translation step is the unit-disk graphs. An arbitrary conflict graph has to be laid out into positions that reproduce it, which is its own hard problem and one nobody solves for you.
The register has to be addressable. Aquila drives atoms in rows, so any two must share a y coordinate exactly or sit at least 4 um apart in y. A regular octagon puts two atoms 3.75 um apart and is refused before submission, and scaling it up until the rows clear 4 um pushes its sides past the blockade so the edges vanish. A ring of 8 is not a shape this machine can hold at any scale; a grid is.
The sweep can miss. It is adiabatic in intent. On harder instances the state can settle in a maximal independent set that is not maximum, exactly as a greedy classical heuristic can. Slower sweeps help and the device caps how slow you can go.
Brute force wins at checkable sizes. Nine items is 512 subsets, instant on any machine. The interesting region starts where exhaustive search stops, and that is also where the answer can no longer be verified, so the approach here is to measure answer quality where checking is possible and carry that curve upward rather than assume it holds.

Run it yourself

Atom positions in, an independent set out. The service builds the sweep, submits it and decodes the answer, and every shot is checked against the edges your own layout creates.

job = client.run_mis(
    vertices=[[0, 0], [6, 0], [12, 0], [0, 6], [6, 6],
              [12, 6], [0, 12], [6, 12], [12, 12]],
    shots=1000, engine="qpu.quera.aquila")

job["result"]["mis"]["best_set"]         # the items to keep
job["result"]["mis"]["valid_fraction"]   # how much to trust it
job["result"]["mis"]["blockade_um"]      # the radius your drive produced

Start on analog.pulser.cpu, which is exact to 14 atoms and costs a hundredth of a cent, and confirm the layout produces the edges you meant before sending anything to hardware. Aquila runs Friday 04:00 UTC to Monday 04:00 UTC, pausing 12:00-13:00 each day and 00:00-01:00 each night, so a submission outside that window is accepted and waits.

The derivation of the blockade radius, and the bug that made a correct machine look wrong, are in maximum independent set on neutral atoms.

Read the docs Benchmark methodology