The concept of quantum computing has existed for over 30 years, with foundational work by Shor (1994) and Grover (1996) on early algorithms. Over the past decade, real quantum machines have emerged (ranging from 5 to 5000 qubits), making it possible to execute these algorithms either directly on a QPU (Quantum Processing Unit) or through emulation on a GPU.
The team naturally turned toward Quantum Operations Research, which aims to solve optimization problems using this new computational paradigm. Eric Bourreau gave a plenary talk on this topic at the ROADEF 2021 conference. Indeed, the quantum approach is based on a completely different philosophy, where decision variables are in superposition, and measurements, through collapse, introduce a stochastic dimension into the interpretation of results.
These optimizations can be carried out:
— Globally, by seeking an optimum,
— Or via local search approximation algorithms known as variational methods.
Several PhD thesis have thus been launched within the team, with a dual ambition:
— To obtain theoretical results on the complexity bounds of scheduling problems;
— To explore industrial use cases, including:
o SNCF (Camille Grange’s defended thesis): railway transport planning
o TotalEnergies (Yagnik Chatterjee’s defended thesis): fleet optimization
o La Poste (Imran Meghazi’s ongoing thesis): impact of quantum machines on future postal challenges.
Finally, the boom in quantum architectures (based on photons, trapped ions, cold atoms, or superconductors) leads to various models of the same combinatorial problems. These different approaches compel us to assess both their current performance and their future scalability.