Optimisation et quantique

Comment maximiser le chargement d’un camion de livraison tout en respectant des contraintes de poids et de volume ? Comment décider de l’ordre dans lequel ce camion va effectuer sa livraison ? Comment découper une grande plaque de verre en plusieurs fenêtres de taille donnée tout en minimisant la surface de verre non utilisée ? Comment déterminer l’emploi du temps d’infirmiers de garde tout en respectant les contraintes réglementaires et en maximisant le respect des souhaits formulés par les infirmiers ? Ces problèmes concernent des domaines bien différents mais peuvent tous être formulés mathématiquement de façon similaire : sous la forme de problèmes d’optimisation.

La recherche opérationnelle est la discipline qui cherche à répondre mathématiquement à ces questions. Mêlant théorie et simulations numériques, la recherche opérationnelle permet de proposer une décision ou un éventail de choix possibles dans le cadre d’un modèle dont les hypothèses sont clairement formulées.

De façon intéressante, certaines techniques d’optimisation utilisées en recherche opérationnelle sont inspirées de phénomènes physiques naturels. Le recuit simulé est un algorithme qui cherche à trouver (ou à approximer) le minimum d’une fonction définie sur un espace de recherche trop grand pour qu’on puisse simplement tester toutes les valeurs possibles. L’inspiration vient d’un procédé de métallurgie qui consiste à refroidir un métal lentement. En effet si on laisse le métal refroidir naturellement, les atomes vont s’agencer de façon régulière à petite échelle mais on trouvera de nombreuses jonctions irrégulières entre deux zones régulières. En revanche un refroidissement suffisamment lent conduit à une seule grande zone régulière: le métal prend sa configuration la plus stable, c’est-à-dire celle qui a la plus basse énergie. On parvient donc à minimiser la fonction énergie d’un métal par un refroidissement lent et des petits déplacements aléatoires de chacun de ses atomes! En interprétant une température élevée comme une probabilité élevée de réaliser un déplacement d’un atome qui fait augmenter l’énergie totale du métal, on peut définir mathématiquement l’algorithme du recuit simulé.

Le recuit simulé permet de trouver efficacement le minimum de nombreux problèmes d’optimisation. Toutefois il peut arriver qu’au bout du temps de calcul maximal autorisé, le recuit simulé n’ait pas trouvé le minimum global du problème mais soit resté bloqué au niveau d’un minimum local (strictement supérieur au minimum global donc). C’est souvent le cas lorsque le minimum global est entouré de larges vallées de minima locaux dont il est séparé par des valeurs élevées de la fonction qu’on cherche à minimiser. Dans ces cas là, il peut être intéressant de considérer le recuit quantique, un autre algorithme d’optimisation. Pour implémenter le recuit quantique, on a besoin de mémoire quantique, c’est-à-dire de qubits (contraction de quantum et de bits). Le recuit quantique utilise la capacité des qubits à être dans un état de superposition pour explorer efficacement l’ensemble de l’espace de recherche. Il offre la possibilité de diminuer la probabilité de présence au niveau d’un minimum local et de l’augmenter au niveau du minimum global par effet tunnel. Il n’y a pas besoin de notion de température dans l’algorithme du recuit quantique car la description de l’état d’un qubit est intrinsèquement probabiliste. En revanche un champ magnétique dit transverse contrôle la propension qu’ont les qubits à se trouver dans un état de superposition. Comme la température dans le cas du recuit simulé, ce champ magnétique transverse est diminué au cours de l’algorithme.

Pour compliquer encore plus les choses :) il est possible de reproduire certaines propriétés du recuit quantique à l’aide d’algorithmes utilisant de la mémoire classique (des bits). Ces techniques forment la famille des algorithmes d’inspiration quantique. Les algorithmes d’inspiration quantique sont probabilistes pour explorer efficacement l’espace de recherche. Ils parviennent à reproduire l’effet tunnel du recuit quantique en faisant dépendre certaines étapes de l’algorithme de propriétés globales de l’espace de recherche et de la fonction qu’on cherche à minimiser. Alors qu’aujourd’hui le hardware quantique n’est disponible qu’en quantité très restreinte et est largement sujet aux erreurs, les algorithmes d’inspiration quantique permettent de profiter dès maintenant de techniques d’optimisation qui définissent le nouvel état de l’art. En outre ils permettent d’exprimer un problème concret sous la forme mathématique qui permettra de le résoudre plus efficacement encore en utilisant le recuit quantique. On parvient ainsi à améliorer les solutions actuelles tout en préparant l’arrivée des ordinateurs dotés d’une mémoire quantique suffisamment importante et fiable. Offrir le meilleur des deux mondes, c’est opportun pour un algorithme d’optimisation!