Pasqal Challenge: Schrodinger's Cats

Inspiration

Every delivery company solves the same puzzle every morning: given a depot, a fleet of trucks with limited capacity, and a list of customers, which truck should visit whom, and in what order? This is the Capacitated Vehicle Routing Problem (CVRP). It's NP-hard, and small versions of it already blow up combinatorially.

Pasqal's neutral-atom devices don't run gates. They are an optimization problem: a register of Rydberg atoms naturally settles into low-energy configurations of an Ising Hamiltonian. We wanted to know whether we could reshape a real logistics problem so the atoms could solve it natively, instead of forcing a textbook formulation onto hardware that can't represent it.

What it does

s-cats-pasqal is an end-to-end cluster-first, route-second CVRP pipeline that runs at pulse level on Pasqal's AnalogDevice emulators:

Generate certified-feasible instances in three tiers (S, M, L), each shipped with a bin-packing certificate and an exact or best-known reference cost $C^\star$.
Track A, clustering: assign customers to vehicles with a QUBO embedded as atom positions and solved by an adiabatic pulse.
Track B, routing: order the stops inside each cluster with a second, compact TSP QUBO.
Evaluate every run against $C^\star$, splitting the end-to-end gap into decomposition, clustering, and routing losses.

How we built it

Matching the hardware. The device evolves under

$$ \frac{H(t)}{\hbar} = \sum_u \frac{\Omega(t)}{2}\,\hat\sigma^x_u \;-\; \delta(t)\sum_u \hat n_u \;+\; \sum_{u<v}\frac{C_6}{\lVert r_u-r_v\rVert^6}\,\hat n_u\hat n_v . $$

At the end of the sweep it samples a QUBO $x^\top Q x$ with only repulsive couplings ($Q_{uv} \ge 0$) and a uniform diagonal (one global detuning). Both of our formulations are designed around those two constraints.

Track A: the "zero-last-vehicle" encoding. Instead of $NK$ one-hot variables plus binary slack for capacity, each customer gets only $K-1$ atoms. An all-zero row means "last vehicle":

$$ x_{i,K-1} = 1 - \sum_{k=0}^{K-2} x_{i,k}. $$

Customers repel when they share a vehicle, with a weight that combines distance and demand:

$$ W_{ij} = \frac{\lVert r_i - r_j\rVert}{100} + P_{\text{cap}}\,\frac{d_i d_j}{Q^2} > 0 . $$

A blockade term keeps each customer on at most one explicit vehicle. This cut the atom count from 14 / 45 / 80 (slack encoding) to 4 / 20 / 45 for Tiers S / M / L. On Tier S, every bitstring is a valid assignment by construction.

Track B: anchor-customer TSP. We fix the customer closest to the depot as the first stop, which breaks the start and reversal symmetry. The standard $n^2$ position encoding becomes $(n-1)^2$, so a 4-stop route needs 9 atoms instead of 16 and fits exact state-vector simulation.

From QUBO to atoms to pulses. We anchor the strongest coupling at $5.4\,\mu\text{m}$ and fit atom positions with L-BFGS-B so that $C_6/r^6$ matches the target couplings, within the device limits $r_{\min} = 5\,\mu\text{m}$ and $R_{\max} = 38\,\mu\text{m}$. The pulse is a $4.4\,\mu\text{s}$ sweep that slows down 3× near the minimum gap, with the final detuning calibrated from the realized interactions. Registers of up to 12 atoms run on QutipBackendV2; larger ones run on the emu-mps tensor-network emulator.

Results

Tier S: 96–100% feasible shots and the exact CVRP optimum on 2 of 3 instances.
Tier M: 32–47% feasible shots vs. 3% for 1,000 uniform random shots, with a 13–21% end-to-end gap.
Tier L: 2–16% feasible shots (random sampling found none), with a 32–63% end-to-end gap.

Challenges we ran into

Over-excitation. Our first pulses drove the detuning to the full QUBO diagonal and lit up multiple atoms per customer. Lowering the final detuning from $0.50\,U_{\text{pair}}$ to $0.45\,U_{\text{pair}}$ restored feasibility on Tier S.
$1/r^6$ is local, our QUBO is dense. On Tier L, every atom should couple to the atoms of 14 other customers at roughly equal strength. A 2D register can't do that, so the embedding reproduces only a fraction of the intended interactions.
Global detuning vs. exact penalties. The zero-last-vehicle expansion produces customer-dependent linear terms. Averaging them into one global detuning was enough on small tiers, but on Tier L a classical check showed it pushes the ground state over capacity.
Simulation scale. Exact simulation stops being practical past about 12 atoms, so Tiers M and L depend on approximate MPS emulation.
Decomposition cost. On one Tier S instance the true optimum puts every customer on one vehicle. Our balanced-clustering model can't express that, so even a perfect sample is 25% off.

What we learned

On analog hardware, the formulation is the algorithm. Atom count, sign structure, and how local the couplings are matter more than the solver.
More adiabatic time can't fix a Hamiltonian whose ground state is infeasible. Checking the realized QUBO classically before emulating saved us a lot of blind pulse tuning.
Two-way splits ($K = 2$, one atom per customer) are remarkably robust to embedding error. That points us toward recursive bisection for large instances.

What's next

Recursive bisection with the $K=2$ encoding for Tiers M and L.
Rigid-polygon embeddings that can't stretch the blockade.
Per-subproblem detuning calibration, and reporting raw and repaired feasibility separately.
Letting the model choose to use fewer vehicles.