Analogue optimisation on Rydberg atom arrays (maximum independent set)
Algorithms and benchmarks / Optimisation
Arrays of neutral atoms excited to Rydberg states cannot excite two close neighbours at once, which maps naturally onto the maximum independent set problem on unit-disk graphs.
- Era
- Analogue or special-purpose
- Problem class
- Optimisation
- Speedup
- Ebadi et al. (2022) report a superlinear quantum speedup in finding exact solutions on the hardest graphs in the deep-circuit regime, against the classical algorithm they chose.
How it works
Atoms are placed by optical tweezers at the vertices of the graph; a laser pulse sequence drives the array towards its ground state, whose excited atoms form an independent set; pulses are tuned in a hybrid loop.
Typical use cases
- Network design, placement and scheduling problems that reduce to independent sets.
Documented use cases on related problems
From the use case directory; the sources of these cases may use other methods than this one.
Resource estimates
No resource estimate with stated assumptions was verified for this family in this release.
Demonstrations
- 2022: Maximum independent set on up to 289 Rydberg-atom qubits in two dimensions. (S. Ebadi et al. 2022)
Hardware platforms that fit
- Neutral atoms: Native to Rydberg atom arrays: up to 289 qubits in two dimensions in Ebadi et al. (2022).
- Analogue quantum simulators: The same programmable analogue arrays serve as quantum simulators.
What you need to run it
- Classical simulation
- Classical solvers for independent sets and emulators of the pulses (Pulser includes one) serve small instances.
- Noisy hardware (NISQ)
- Not applicable for this family.
- Fault-tolerant machine
- Not applicable for this family.
- Annealer or analogue simulator
- A neutral-atom array with programmable geometry and Rydberg pulses; hundreds of atoms in the cited work.
Calculate the memory of a simulation
Where to run it in Europe
Neutral atoms
- JADE (Germany; Inaugurated, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. No access route named in the catalogue. Deployment milestones JADE
- Ruby (France; Inaugurated, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones Ruby
- SOL (Italy; Planned, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. No access route named in the catalogue. Deployment milestones SOL
- LRZ Quantum Integration Centre (QIC) (Germany; In operation, per the source): Superconducting systems from IQM (54 qubits, up to 150 in future), a 20-qubit AQT ion-trap system, and a neutral-atom system being developed by planqc (MAQCS project). Access: LRZ quantum computing consulting.
- France Hybrid HPC Quantum Initiative (HQI) platform (France; In operation, per the source): Hybrid HPC–quantum platform coupled to the Joliot-Curie supercomputer: Ruby (analogue neutral-atom system controlling 100 rubidium atoms), Lucy (12-photon photonic QPU) and Qaptiva QPU emulation. Access: GENCI eDARI resource allocation requests. Deployment milestones France Hybrid HPC Quantum Initiative (HQI) platform
Analogue quantum simulators
- JADE (Germany; Inaugurated, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. No access route named in the catalogue. Deployment milestones JADE
- Ruby (France; Inaugurated, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones Ruby
- SOL (Italy; Planned, per the EuroHPC JU): Neutral atoms; analogue/digital quantum simulator. No access route named in the catalogue. Deployment milestones SOL
The full infrastructure catalogue · The infrastructure deployment tracker
Software
European tools in the software directory
Other open-source frameworks
- Bloqade (QuEra Computing (United States); non-European)
A listing is not an endorsement; check each tool for the features you need.
Limitations and open questions
- Only graphs that fit the geometry of the array map directly; others need encodings with overhead.
- The reported speedup is relative to a specific classical algorithm on selected graph instances.
In the Quantum Algorithm Zoo
- Adiabatic Algorithms (Quantum Algorithm Zoo, external site): Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: A plausible superpolynomial example is cited
Closest Zoo entry; the Zoo describes adiabatic algorithms in general, not Rydberg arrays.
Index: the Quantum Algorithm Zoo by Stephen P. Jordan, last updated 2026-09-10, checked 2026-10-23. The portal links to it and copies no description from it. Browse the full Quantum Algorithm Zoo (external site)
Named in European procurements
- Used in: EuroHPC procurement EuroQCS-Italy (now SOL) (Required in the benchmark suite (scored under the award criteria))
As the tender documents state; how a benchmark is weighted against others is described in each procurement.
Sources
- S. Ebadi et al. (2022). Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays. Science 376, 1209 (2022); arXiv:2202.09372. Read: abstract page, retrieved 2026-10-23.