Maximum Independent Set on Neutral Atoms

Everything here is runnable on your own circuit. Try it in the console

Most quantum optimisation demonstrations encode a problem into a Hamiltonian, add penalty terms to enforce the constraints, and hope the penalties are weighted well enough that the answer respects them. Maximum independent set on neutral atoms does not work that way, and it is the one case where the hardware and the problem genuinely fit.

The Rydberg blockade forbids two atoms within a certain radius from both being excited. That is not an encoding of the independent-set constraint. It is the constraint, enforced by physics rather than by an energy penalty you tuned.

Measured on QuEra Aquila

Nine atoms on a 3x3 grid at 6 um spacing, 1,000 shots, on real quantum hardware: QuEra Aquila, a quantum processing unit (QPU) holding 256 neutral atoms. 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 3x3 board: 9 vertices, 20 edges. The optimum is checkable by hand, since the four corners are 12 um apart and outside the blockade, and no independent set of five exists.

What was sampled: each shot is one candidate set, an atom measured in the Rydberg state being a vertex chosen. Every shot is checked against the edge list, and shots that violate an edge are excluded from the answer and counted separately.

device          QuEra Aquila, 256-atom neutral atom
graph           3x3 grid at 6 um, the king's graph: 9 atoms, 20 edges
shots           1,000 requested, 947 returned
found           [0, 2, 6, 8], size 4
true optimum    4, the four corners
valid shots     883 of 947    93.2%
optimal shots   574 of 947    60.6%
set sizes       1: 16   2: 58   3: 235   4: 574   (valid shots only)

Click to enlarge

Close

The valid-shot fraction is the figure to read first. On the exact simulator below, every shot in every run was valid; on hardware 64 shots of 947 violated an edge. Validity and optimality stay separate questions: 883 shots obeyed the constraint, and 574 of those also found the largest set.

Both of those runs are in the table below. The emulator and the hardware were given the identical 3x3 register, which is what makes the two rows a comparison rather than two separate results.

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. On 25 September the identical sequence ran on analog.pulser.gpu, an NVIDIA GPU, returning the same set with all 500 shots valid. Submitted to each kind of compute we offer, on 18 and 25 September 2026. Every figure below is a real job on the service, priced as any customer would be priced.

Device	Engine	Kind	Qubits	Result	Cost
	analog.pulser.cpu	CPU	9	found [0, 2, 6, 8], size 4; 500 of 500 shots valid	$0.0001
	analog.pulser.gpu	GPU	9	found [0, 2, 6, 8], size 4; 500 of 500 shots valid certificate	$0.0017
	qpu.quera.aquila	QPU	9	found [0, 2, 6, 8], size 4; 883 of 947 shots valid, 574 optimal•best 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	—

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.

Pasqal's FRESNEL takes the identical Pulser sequence and is deliberately left without a figure. It is billed as machine time at one shot per four seconds, so a run at this shot count would not be comparable on cost. The sector write-up is on scheduling and allocation.

One device rule shaped the layout. Aquila addresses atoms in rows, so any two atoms 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 in y and is refused before submission, and scaling that octagon up until its rows clear 4 um pushes the sides past the 10.03 um blockade so the edges disappear. A ring of 8 is not a shape this machine can hold; a grid is.

The problem

Given a graph, find the largest set of vertices with no edge between any two of them. Scheduling problems are this: the largest set of tasks with no two in conflict. So is channel allocation, and so is siting transmitters that interfere when too close together. It is NP-hard in general, meaning no known method solves every instance in time that grows polynomially with the number of vertices. On gate hardware it is usually attacked by rewriting the problem as a QUBO, a quadratic unconstrained binary optimisation, in which every constraint becomes an energy penalty, and then running QAOA over it, the quantum approximate optimisation algorithm, whose penalty weights have to be tuned well enough that the answer respects the constraints. Neutral atoms do not work this way.

How the machine encodes it

Each vertex becomes an atom. Two atoms are connected when they sit within the blockade radius of each other. Then:

• Start every atom in the ground state, with the laser detuned well below resonance so being excited is unfavourable
• Ramp the drive on and sweep the detuning upwards, so excitation becomes favourable
• The blockade forbids neighbours from both being excited, so the state that survives is an independent set
• Ramp the drive off and measure. Excited atoms are your chosen set

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

The blockade radius is not a number you choose

This is the part that cost us an afternoon, and it is the most useful thing in this post.

The radius follows from the drive:

R_b = (C6 / Omega)^(1/6)

C6 is a property of the Rydberg state the device uses, and Omega is the Rabi amplitude of your sweep. On the device we build these sequences against, C6 / hbar is 12,241,414 rad/us x um^6, so at our default 12 rad/us drive the radius is 10.03 um.

Our code had 7.5 um hardcoded. The consequence was not a crash, which is why it survived review. The machine dutifully solved a graph in which every pair within 10 um was connected, while the answer we handed back described a graph in which only pairs within 7.5 um were. Pairs sitting 8.5 um apart were blockaded in reality and reported as unconnected.

We found it by running a star: one atom in the middle, four leaves at 6 um around it. As reported, the leaves were mutually unconnected, so the maximum independent set was the four leaves. The machine returned two. Four different remedies, including a slower sweep and vertex weighting, all returned two.

Four identical failures point at the bookkeeping rather than the physics, and so it proved. At the true 10.03 um radius the leaves are 8.49 um apart and therefore connected to each other. The graph is a wheel, its maximum independent set is two opposite leaves, and that is exactly what the machine had been returning all along. It was right and we were wrong.

The measurement

Six graphs, run on an exact neutral-atom simulator at 500 shots each, decoded by checking every shot against the edge list and keeping the largest valid set. The right-hand column is the true optimum from exhaustive search.

graph          atoms  edges  found  true  valid shots  seconds
path of 4          4      3      2     2       100%       0.1
path of 6          6      5      3     3       100%       0.4
3x2 grid           6     11      2     2       100%       0.8
ring of 6          6      6      3     3       100%       0.4
star of 5          5      8      2     2       100%       0.4
two clusters       6      6      2     2       100%       1.3

Six out of six, and every shot in every run was a valid independent set. That last column is worth its own note. The blockade is doing its job perfectly, and "100% valid" says nothing about whether the sets found were the largest ones. Validity and optimality are separate questions, and only the comparison against brute force answers the second.

Where this stops being useful

Three limits, all real.

• The graph is not an input. You give positions; the edges follow from the geometry. The family that maps without any translation step is the unit-disk graphs. An arbitrary graph has to be laid out into positions that reproduce it, which is its own hard problem, and one nobody solves for you
• The sweep can miss. It is adiabatic in intent. On harder instances the state can end in a maximal independent set that is not maximum, exactly the way a greedy classical heuristic can. Slower sweeps help, and the device caps how slow you can go
• Brute force wins at this size. Six atoms is trivial classically. The interesting region starts where exhaustive search stops, and that is where the honest comparison has to be made rather than asserted

The last one deserves emphasis: at the sizes where the answer can be checked, a classical method already finds it.

At the sizes where you would need it, you cannot check the answer. The way through is to measure the quality of the answers where checking is possible, and carry that curve upwards rather than assuming it holds.

Running it

Our neutral-atom path takes atom positions and does the sweep construction for you, on the local emulator up to 14 atoms and on QuEra Aquila up to 256.

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

job["result"]["mis"]["best_set"]        # the vertices to keep
job["result"]["mis"]["valid_fraction"]  # share of shots obeying every edge
job["result"]["mis"]["blockade_um"]     # the radius your drive produced

Start on the emulator. It costs a hundredth of a cent, has no queue, and it is where you confirm your geometry encodes the problem you meant, which is the step this post exists to warn you about. 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 is accepted and waits.

What it costs to rent one has the per-shot pricing, and the Rydberg blockade measured shows the same physical effect producing antiferromagnetic order on a chain.