Spending Fewer Atoms: Slack-Free One-Hot Clustering of the CVRP on an Analog Neutral-Atom Register

Team Qualies — DuQuantum Hackathon, Pasqal challenge "Analog quantum devices for optimization problems" (brief v3.0, 24 Oct 2026). Track A (capacity-feasible clustering) is the primary submission; Track B (clustering + intra-cluster routing) is a complete, honestly-labelled supplementary slice.

One-command reproduction of the headline row:

python -m pip install -r requirements.txt      # exact pins (Python 3.11+; hackathon venv is 3.14)
python scripts/make.py demo                    # validate instances, assert device limits, run S_seed00 on
                                               # pulser-simulation (QuTiP) + random sampler, 500 shots,
                                               # write out/demo/*.json and out/demo/results_demo.csv

The demo runs python -m cvrp.run --instance instances/S_seed00.json --formulation onehot-ub --embedder polygons --backend qutip --shots 500 --seed 0 on the committed register in embeddings/. The register, the pulse and every classical number reproduce exactly; emulator sampling reproduces to sampling noise (TV ≈ 0.05 at 500 shots).

Contents

1. What we built and how each step improved it
2. The problem and the decomposition (Derive 2.1)
3. What the register minimises (Derive 3.1)
4. The clustering model: one-hot, no slack (Task A1)
5. Variable accounting (Derive 4.1)
6. Instances, certificates and reference values (Task A2)
7. Embedding (Task A3)
8. Pulse shaping (Task A4)
9. Results in full (brief §9)
10. Track B: routing (Tasks B1–B3)
11. What did not work
12. Use of AI
13. Repository map and how to reproduce everything
14. Deliverable checklist (brief §10)

1. What we built and how each step improved it

We encoded the capacity-feasible clustering of customers onto vehicles with one atom per (customer, vehicle) pair and no slack atoms: 8 / 30 / 60 atoms on tiers S / M / L, where the textbook slack encoding needs 14 / 45 / 80. The capacity inequality is handled by unbalanced penalization, which on valid (one-hot) strings collapses exactly to a load-balance coupling, so every coupling is positive and every linear term is equal — the model runs on one global detuning, with no DMM. We then built the pieces needed to make the register actually sample this model, and measured every change before and after. The result is a pipeline that returns the model-optimal clustering in 89–99 % of raw shots on every tier-S instance, decodes 98–100 % of shots on tier M, and produces capacity-feasible clusterings in 14–23 % of shots on the 60-atom tier L.

The improvement ladder. Each row was measured on the same instances and committed registers before and after the change (raw shots, 500 per row, no repair). P(opt) is the fraction of shots that are the model-optimal clustering; values are per instance in the order listed.

Best final row per tier (brief Table 3 metrics; every gap on feasible decodes only):

All quantum numbers are raw shots: no repair, no DMM, no post-selection other than discarding infeasible decodes (which never contribute a cost). Repair rows exist and are labelled separately (§9.6). Classical and random reference points requested by brief §9.2 are given in §9 as context.

Built With

• python