Coloriage quantique

Par Mathis Beaudoin, étudiant au baccalauréat en sciences de l’information quantique et stagiaire à l’AlgoLab été 2023

La théorie des graphes est une branche des mathématiques et de l’informatique qui étudie les relations entre des objets connectés. En quelque sorte, il s’agit de l’étude des réseaux et en permet l’analyse ainsi que la modélisation. Bien qu’on puisse décrire un graphe de manière mathématique, on utilise souvent une représentation visuelle composée d’un ensemble de points (appelés nœuds) et de liens (appelés arêtes) reliant ces points. Par exemple, un graphe permet de représenter facilement les frontières communes des pays du monde.

Figure 1 – Graphe représentant les frontières communes de quelques pays d’Amérique du Sud

En théorie des graphes, il existe un problème d’optimisation combinatoire intéressant nommé MaxCut. L’exercice de MaxCut consiste à colorier, avec 2 couleurs différentes, les nœuds d’un graphe de telle sorte que les nœuds d’une arête soient le plus souvent d’une couleur différente. Parmi toutes les façons possibles de colorier les nœuds, seulement quelques-unes satisferont cette condition de MaxCut. Logiquement, une coloration parfaite fait en sorte que pour toutes les arêtes, leurs nœuds sont chacun d’une couleur différente. Dans ce cas, la solution est facile à trouver. Par contre, il est rare que ce cas se produise pour un graphe quelconque et il faut alors faire des compromis pour obtenir des solutions s’en rapprochant. À ce moment, la recherche de solutions peut être fastidieuse, surtout avec des graphes complexes où il y a beaucoup de nœuds et d’arêtes à prendre en compte. Des algorithmes classiques existent pour résoudre MaxCut, mais ceux-ci demandent beaucoup de temps et de ressources afin d’avoir une solution exacte. Alors, on préfère utiliser des méthodes approximatives pour avoir des réponses approximatives dans un délai raisonnable. Cependant, un algorithme quantique nommé QAOA semble être un excellent candidat pour trouver les solutions satisfaisant MaxCut.

Figure 2 – Exemple de solutions pour le graphe à la figure 1

QAOA

QAOA (Quantum Approximate Optimisation Algorithm) est un algorithme quantique permettant de résoudre des problèmes d’optimisation combinatoires. Comme MaxCut est un problème d’optimisation combinatoire, il est possible d’utiliser QAOA pour le résoudre. L’avantage potentiel de QAOA sur les algorithmes classiques repose surtout dans les concepts physiques qu’il utilise et ceux-ci seront décrits dans les prochaines sections.

Hamiltonien

L’hamiltonien est un objet mathématique qui permet de décrire l’énergie d’un système quantique. Comme tout ce qui est quantique, les énergies du système sont séparées en des niveaux distincts et le système peut se trouver dans l’un de ces niveaux ou dans une superposition de ceux-ci.  L’hamiltonien d’un système quantique n’est pas nécessairement fixe dans le temps, ce qui signifie que les niveaux d’énergie peuvent changer à différents instants. Parmi tous ces niveaux, nous nous intéressons au niveau de plus faible énergie qu’on appelle l’état fondamental du système.

Figure 3 – Diagramme d’énergie pour un système quantique quelconque

État fondamental et théorème adiabatique

Le théorème adiabatique est un théorème de la mécanique quantique qui considère un hamiltonien qui change dans le temps afin de proposer un résultat intéressant. En effet, il affirme que si le système se trouve initialement dans l’état fondamental et que l’hamiltonien évolue suffisamment lentement, alors le système restera dans l’état fondamental bien que celui-ci puisse différer avant et après les modifications. QAOA se base sur ce résultat afin de résoudre des problèmes d’optimisation combinatoires.

QAOA pour résoudre MaxCut

Pour résoudre MaxCut avec QAOA, on commence avec un hamiltonien A dont l’état fondamental est connu et qui peut être facilement obtenu par un circuit quantique. Ensuite, on construit mathématiquement un nouvel hamiltonien B à partir de la configuration du graphe qu’on veut résoudre de telle sorte que son état fondamental correspond aux solutions de MaxCut. Contrairement à l’hamiltonien A, l’état fondamental de l’hamiltonien B n’est pas connu et il est très complexe de faire des calculs mathématiques pour le connaitre. Donc, on fait évoluer l’hamiltonien A vers l’hamiltonien B de manière à respecter du mieux possible le théorème adiabatique et on mesure le système après la transformation. Selon le théorème adiabatique, les états ayant les plus grandes probabilités d’être mesurés correspondront aux solutions de MaxCut pour le graphe en question.

L’algorithme classique le plus simple pour résoudre MaxCut consiste à tester tous les coloriages possibles pour un graphe donné et de voir quels sont les meilleurs au fur et à mesure. Comme le nombre de façons de colorier un graphe croît exponentiellement avec son nombre de nœuds, ce processus demande rapidement beaucoup de temps et de ressources. Autrement, il existe des algorithmes classiques donnant des résultats approximatifs pour que la recherche s’effectue dans un délai raisonnable. D’un autre côté, la grande force de QAOA est qu’il n’y a pas de recherche qui est effectuée parmi toutes les solutions possibles. En effet, les solutions sont encodées dans l’état fondamental de l’hamiltonien B et il ne suffit que de suivre le théorème adiabatique pour y avoir accès.

Ainsi, QAOA est beaucoup moins demandant en temps et en ressources comparativement aux algorithmes classiques. Malgré cela, QAOA ne permet pas d’obtenir les résultats attendus sur les ordinateurs quantiques actuels et ce même pour des graphes très simples. Il serait donc intéressant de trouver une méthode alternative capable de fonctionner sur les ordinateurs quantiques du présent en attendant une nouvelle génération d’ordinateurs quantiques.