Millions of electric vehicles will soon plug in every evening. Deciding who charges where and when is a hard graph problem, the Maximum Independent Set, and a natural playground for networked quantum processors.
The evening peak
Electric mobility is central to the energy transition, but it brings a new challenge for grid operators: if every driver plugs in on arriving home, demand peaks at the worst possible moment. Smart charging means scheduling charging sessions, assigning each vehicle a charger and a time slot, so that as many vehicles as possible are served while respecting the time windows requested by drivers and the capacity of chargers and of the local grid.
From a car park to a graph
This scheduling problem has an elegant translation into graph theory (Figure 1). Each possible assignment, “vehicle V on charger C during interval T”, becomes a vertex. Two vertices are joined by an edge when they cannot both be chosen: either they concern the same vehicle, which needs to be charged only once, or they occupy the same charger at overlapping times. A feasible schedule is then exactly an independent set, a set of vertices with no edge between them, and the schedule serving the most vehicles is a Maximum Independent Set (MIS). Priorities or energy volumes can be added as weights on the vertices.
The MIS problem is NP-hard: the number of candidate subsets grows exponentially, and for large instances classical solvers fall back on heuristics without any guarantee of optimality.

A problem quantum hardware speaks natively
MIS is one of the most natural problems for quantum processors. On neutral-atom machines, each vertex is an atom, and the Rydberg blockade prevents two nearby atoms from being excited at the same time: the hardware enforces the independence constraint by itself. A carefully shaped laser pulse then drives the atoms towards configurations with as many excited atoms as possible, that is, large independent sets. On gate-based processors, the same problem is tackled with the Quantum Approximate Optimisation Algorithm (QAOA). EDF and Pasqal have already applied these methods to smart-charging instances built from real data, with experiments on up to 100 qubits.
Why distributed quantum computing
City-scale instances, with thousands of vehicles, many charging hubs and dozens of time slots, produce graphs far larger than any single quantum processor can host. Fortunately, these graphs are naturally clustered: vehicles compete mostly with others at the same hub and in the same time window. This is precisely the structure that distributed quantum computing exploits. Welinq and EDS, along with Pasqal, aim to treat the problem in an approach through partitioning across several networked QPUs so that only a handful of constraints cross between processors (Figure 2). These boundary constraints are handled with entanglement distributed through Welinq’s quantum links, combined with classical coordination, so that local solutions assemble into one consistent schedule.

Looking ahead
In the AQADOC project, we are developing and benchmarking distributed MIS algorithms on smart-charging scenarios of increasing size, measuring how solution quality evolves with the number of processors and the entanglement budget. The direction is clear: as modular quantum hardware grows, so will the charging networks we can optimise, bringing closer a future where quantum computers help keep electric mobility convenient for drivers and gentle on the grid.

