L’informatique quantique pourra-t-elle résoudre les problèmes d’optimisation ?

L’informatique quantique : un domaine en pleine croissance

Les Nations Unies ont déclaré l’année 2025 « Année des sciences et des technologies quantiques » afin de mettre en avant les progrès de la physique quantique depuis ses débuts il y a cent ans. Ceux-ci irriguent désormais des domaines au-delà de la physique, dont l’informatique, en offrant notamment de nouveaux paradigmes de calcul. 

Dans les années 1990, le théoricien de l’informatique quantique Peter Shor a conçu un algorithme utilisable par un futur ordinateur quantique pour factoriser des nombres de manière bien plus efficace qu’un algorithme classique. Depuis cette époque, l’algorithmique quantique est devenue une discipline en plein essor, qui ouvre des perspectives sur d’autres types de problèmes, comme ceux d’optimisation, le cœur de recherche de l’équipe-projet Bonus au Centre Inria de Lille. 

L’optimisation pour répondre à des problèmes complexes

Dit simplement, l’optimisation consiste à trouver les solutions qui maximisent ou minimisent une quantité qui nous intéresse, définie par une fonction mathématique. Lorsque la résolution exacte d’un problème n’est pas possible, du fait de sa complexité trop grande, « il faut trouver un compromis entre le temps de calcul nécessaire et la qualité de la solution approximative trouvée », explique Zakaria Abdelmoiz Dahi, chercheur de l’équipe-projet Bonus. 

Parmi ces problèmes figure "l’optimisation multiobjectif" qui nécessite d’optimiser plusieurs quantités, souvent en contradiction les unes avec les autres. Par exemple, comment faire pour qu’une flotte de camions desserve le maximum de clients tout en consommant le moins de carburant possible ?

De nombreux problèmes concrets relèvent de l’optimisation et les applications sont variées : pour les réseaux de transport ou d’énergie, ou encore la logistique. Des algorithmes d’optimisation existent ainsi déjà, comme NSGA-II. Toutefois, l’informatique quantique pourrait-elle en concevoir de plus efficaces ?

L’algorithmique quantique au cœur des défis

Premier constat, il n’est pas toujours possible de transposer simplement un algorithme classique en un algorithme quantique. Les paradigmes de calcul sont radicalement différents. Par exemple, le calcul classique se base sur des quantités binaires, les bits, qui ne peuvent prendre que deux valeurs. De l’autre côté, la physique quantique permet d’utiliser des qubits (pour bits quantiques) qui peuvent se placer dans des superpositions « à la fois 0 et 1 », c’est-à-dire prendre tout un continuum de valeurs. 

Et le nombre d’états que l’on peut représenter croît exponentiellement avec le nombre de qubits, c’est-à-dire bien plus rapidement que dans le cas classique. Une autre propriété quantique, l’intrication, offre la possibilité de faire des liens entre les informations de ces qubits (des corrélations) qui sont impossibles à réaliser avec des bits classiques.

Le parallélisme des algorithmes quantiques est donc d’une toute autre nature et laisse entrevoir des accélérations de calculs bien au-delà de ce qui est possible avec les ordinateurs standard. « Mais ces caractéristiques ne font pas tout, nuance Zakaria Abdelmoiz Dahi. Tout l’art réside dans la conception des algorithmes. »

Des ordinateurs quantiques encore limités

Depuis plus de dix ans environ, les premiers ordinateurs quantiques ont commencé à sortir des laboratoires, soit via des grands acteurs finançant des activités sur le sujet (Google, IBM, etc..), soit via des entreprises spin-off de groupes de recherche. Ils utilisent différentes technologies pour réaliser les qubits (circuits supraconducteurs, atomes ou ions piégés, photons, etc.).

Mais, si les progrès sont rapides, ce sont encore des prototypes dont les qubits sont en nombre limités et surtout « bruités », car les effets quantiques (superposition, intrication) sont très sensibles aux perturbations et difficiles à maintenir et à manipuler. 

Les spécialistes parlent de machines NISQ (Noisy Intermediate Scale Quantum), soit des machines quantiques bruitées de taille intermédiaire, pour qualifier les ordinateurs quantiques actuels. « Il faut prendre ces problèmes en considération, car un mauvais design rend l’algorithme inutilisable », pointe le chercheur.

Vers une optimisation multiobjectif

Aujourd’hui, des algorithmes quantiques pour s’attaquer aux problèmes d’optimisation existent déjà, en particulier le QAOA (Quantum Approximate Optimization Algorithm). Cependant, ce dernier ne s’applique qu’à des problèmes « mono-objectif ». Dans un article récent publié avec des collègues de l’université de Malaga, Zakaria Abdelmoiz Dahi s’est attaché à étendre cet algorithme, non pas à un problème pratique en particulier, mais à une classe de problèmes multiobjectif.

Le QAOA fonctionne grâce à un concept de physique quantique, le théorème adiabatique. En quoi consiste-t-il ? En physique, le concept d’"hamiltonien" décrit l'énergie totale d'un système entier (ici, l’état de l’ensemble des qubits). Le théorème adiabatique assure que, si ce système se situe dans son état d’énergie minimale et qu’il évolue de façon suffisamment contrôlée, alors il restera dans son état d’énergie minimale même si son hamiltonien change. 

Le principe du QAOA est de faire correspondre la solution du problème avec cet état d’énergie minimale qui peut être mesuré. L’art de l’algorithme est ensuite d’effectuer une série d’opérations (des portes logiques quantiques) sur les qubits pour amener le système dans la configuration souhaitée. 

Forces et faiblesses des algorithmes quantiques

Le travail de Zakaria Abdelmoiz Dahi et de ses collègues pour généraliser cet algorithme a suivi plusieurs étapes. D’abord, ils ont établi une formulation mathématique pouvant intégrer tous les objectifs, assimilable par l’algorithme. Autre objectif atteint : conserver l’optimalité permise par le théorème adiabatique. 

Surtout, les scientifiques se sont assurés que l’algorithme soit adapté aux machines actuelles et implémentable. « Cette étape a considérablement augmenté la complexité du travail », confie le chercheur. Enfin, l’algorithme a été testé à la fois sur des supercalculateurs classiques suffisamment puissants pour simuler le comportement d’un petit ordinateur quantique et sur de véritables ordinateurs quantiques de 127 qubits d’IBM accessibles via le cloud.

L’ambition de cette recherche n’était pas de démontrer un avantage quantique direct de cette méthode par rapport aux algorithmes classiques, du fait de la nature limitée des ordinateurs quantiques actuels. Il s’agissait plutôt de poser des bases réutilisables par la suite sur des systèmes plus performants. Autre finalité : faire le point sur les forces, les faiblesses et l’applicabilité des algorithmes quantiques dans ce cas particulier.

Le "recuit simulé quantique" pour l’optimisation

Sur leur lancée, Zakaria Abdelmoiz Dahi et ses collègues ont encore étendu ce travail dernièrement, en utilisant un autre paradigme de calcul quantique. Au lieu de manipuler les qubits par des opérations successives, l’évolution se fait ici de manière continue. Cette technique, appelée "recuit simulé quantique", n’est pas aussi polyvalente que celle fonctionnant avec des portes logiques quantiques, mais elle se révèle très adaptée aux problèmes d’optimisation.  

En collaboration avec le laboratoire QAR-lab de l’université Ludwig-Maximilians de Münich, l’algorithme d’optimisation a pu être testé sur les ordinateurs de l’entreprise canadienne D-Wave qui utilisent cette technique. « Les résultats sont très prometteurs, se réjouit Zakaria Abdelmoiz Dahi. Nous espérons les publier prochainement. »