Optimiser votre voyage grâce à la quantique
Par Elisabeth Mailhot
Avez-vous déjà tenté de planifier un voyage, mais il y avait tellement d’endroits que vous vouliez visiter que vous ne saviez pas comment bien planifier votre itinéraire? Si c’est le cas, alors vous avez déjà été confronté au classique problème d’optimisation du commis voyageur (Traveling salesperson problem).
Le problème s’énonce comme suit : imaginons un commerçant qui se promène de ville en ville. Celui-ci a sa liste de villes à visiter, les routes les reliant entre elles ainsi que la longueur de ces routes. Pour être efficace, le commerçant veut trouver un itinéraire qui passe par toutes les villes une seule fois et le ramène à son point de départ le plus rapidement possible, un peu comme vous lors de votre voyage! Afin de trouver le meilleur chemin à prendre, il doit considérer toutes les options possibles. Cela ne semble pas si mal si l’on a seulement trois ou quatre villes à visiter, mais le nombre d’options augmente très rapidement avec le nombre de villes et personne n’a le temps de considérer des millions de possibilités! Alors, comment peut-on résoudre ce problème?
Premièrement, nous pouvons transformer notre problème en un graphe, un ensemble d’éléments représentés par des nœuds reliés entre eux par des arêtes. Nos villes seront donc nos nœuds du graphe et les arêtes représenteront les routes. Ces arêtes auront ce qu’on appelle un poids, une valeur associée, qui sera dans ce cas-ci la distance à parcourir. Nous pourrions donc avoir un graphe qui ressemble à la figure 1 ci-dessous.
Maintenant que nous avons notre graphe, nous pouvons nous attaquer au problème. Il existe différentes manières de s’y prendre, mais une seule méthode, à ce jour, permet de trouver le chemin optimal à coup sûr. Cette approche est celle de la force brute, c’est-à-dire d’énumérer toutes les options de chemins possibles. C’est une approche simple, mais qui requiert beaucoup de temps et qui devient vite impossible à réaliser lorsque le nombre de villes augmente. En effet, pour seulement quinze villes toutes reliées entre elles, il y aurait 43 589 145 600 itinéraires potentiels à vérifier!
Il faut donc se tourner vers des heuristiques, soit des algorithmes permettant de résoudre rapidement des problèmes complexes en menant à de bonnes solutions, mais pas nécessairement à la meilleure. Un exemple d’heuristique pour résoudre le problème du commis voyageur est celui du plus proche voisin. Dans cette méthode, nous commençons avec une ville de départ, un point du graphe, au hasard. Puis, la prochaine ville est choisie selon le poids de l’arête adjacente la plus basse, donc de la distance la plus courte. Et ainsi de suite pour chaque ville, en ne choisissant jamais une arête menant à une ville déjà visitée. Lorsque la dernière ville est atteinte, on prend le chemin pour revenir au sommet de départ. Cela devrait donner un chemin de longueur totale qui s’approche de la solution optimale.
Coup de pouce quantique
Ainsi, il existe des algorithmes qui offrent de bonnes solutions, mais pouvons-nous faire mieux à l’aide des ordinateurs quantiques? C’est la question que certains scientifiques se posent et à laquelle ils tentent de répondre. En effet, grâce aux ordinateurs quantiques et à leur capacité à exploiter des phénomènes quantiques, il y aurait possibilité de réaliser ces calculs complexes plus facilement! Prenons la superposition, l’un de ces phénomènes très intéressants. Rappelons que les ordinateurs que nous utilisons dans la vie de tous les jours ont leur propre langage pour l’information, le binaire, composé de ‘0’ et de ‘1’. Une unité d’information qui prend l’une ou l’autre de ces deux valeurs se nomme un bit. Cependant, pour les ordinateurs quantiques, c’est un peu différent. Les bits deviennent ce qu’on appelle des qubits qui peuvent aussi prendre les valeurs ‘0’, ou‘1’, mais qui peuvent également être en superposition de ces deux valeurs en même temps. Cela permet d’explorer plusieurs possibilités à la fois ou, dans notre cas, plusieurs itinéraires.
Maintenant, découvrons l’un de ces fameux algorithmes quantiques qui pourraient aider à résoudre le problème du commis voyageur, l’algorithme de Grover. Tout d’abord, tous les qubits sont mis en superposition d’états pour représenter tous les itinéraires existants entre les villes. Ensuite, l’algorithme est divisé en deux étapes importantes : l’oracle et le diffuseur. L’oracle vient cibler les solutions possibles selon les conditions du problème qui sont, dans notre cas, de visiter une ville à la fois et de les visiter une seule fois. Le diffuseur vient quant à lui augmenter les probabilités d’obtenir certaines solutions, et ce, en deux phases : trouver les solutions valides, puis celles qui sont minimales. On effectue l’algorithme un grand nombre de fois et la solution qu’on obtient le plus souvent devrait être le meilleur itinéraire.
Bien sûr, les ordinateurs quantiques que nous avons présentement ne fonctionnent pas parfaitement. Par conséquent, les algorithmes comme ceux de Grover fonctionnent bien en théorie, mais moins en pratique. Mais lorsque ceux-ci seront au point, possiblement dans quelques années, vous serez prêts. À vos ordinateurs, c’est l’heure de se mettre aux algorithmes quantiques pour concevoir votre voyage optimal!