Maximum Independent Set on a Neutral-Atom Quantum Computer

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.

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.

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.

If you take one thing from this post: derive your blockade radius from your drive before you lay out a problem. A radius that disagrees with your pulse describes a graph the machine is not solving, and the failure is silent because every answer it gives is a valid independent set of the real graph.

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, because it is where most quantum optimisation claims quietly fail. At the sizes where you can check the answer, you did not need the quantum computer. 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 tenth 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 in weekend execution windows, so a weekday submission 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.