Si l’intelligence n’en est qu’à ses prémisses, les limitations de vitesse de calcul se font déjà ressentir sur des jeux de données conséquents. L’algorithmie quantique appliquée à l’IA, telle que proposée par une équipe de l’Université Nationale de Singapour, pourrait permettre d’augmenter considérablement la puissance de calcul grâce à un nouvel algorithme (amélioration d’un de 2009) dédié aux systèmes linéaires !

La physique quantique étant complexe et « illogique », on va d’abord vous la présenter avant de parler plus en détail de l’IA quantique. Si vous n’avez pas besoin d’explications, allez directement à la deuxième partie.

Qu’est-ce que l’algorithmie quantique ?

Le sujet étant très vaste, on va essayer d’aller à l’essentiel pour que l’article reste compréhensible et pertinent.

La magie quantique

La physique quantique s’appuie sur les lois de la mécanique quantique qui peuvent paraître « magiques » pour nous tant les règles de l’infiniment petit (contre-intuitives, illogiques pour nous) n’ont rien à voir avec celles de notre monde macroscopique… Comme on va le voir :

  • Principe de superposition (sur lequel tout va s’appuyer dans la partie suivante) : rendu célèbre grâce au chat de Schrödinger, une particule peut être à plusieurs endroits en même temps. Contrairement à un ballon de football qui est à un endroit précis du terrain, une particule va être « un peu partout » (mais plus probablement à certains endroits qu’à d’autres), et c’est en regardant où elle est qu’elle va choisir sa position.
  • Indéterminisme de la mesure : découvert par Heisenberg, ce principe stipule qu’on ne peut jamais connaître la position exacte ET la vitesse exacte d’une particule en même temps. Soit on a l’un, soit l’autre, mais jamais les deux à la fois : on aura simplement une probabilité d’avoir telle vitesse si on est à tel endroit (ou vice-versa).
  • Dualité onde/corpuscule : la lumière, et plus généralement toute particule, se comporte à la fois comme une onde (électromagnétique) et une particule (ponctuelle dans l’espace). Il est difficilement concevable d’être les deux en même temps, sachant que l’un des deux « états » l’emporte au moment de la mesure.
  • Effet tunnel : il est possible pour une particule de traverser des obstacles « comme par magie » grâce à la propriété ondulatoire. De la même manière que des ondes sonores traversent faiblement un mur, la probabilité qu’une particule quelconque traverse de la matière et se retrouve de l’autre côté n’est pas nulle. Une bonne explication pour comprendre est donnée juste en-dessous.
  • Intégrale de chemin : une particule pour aller du point A au point B emprunte tous les chemins disponibles (comme par exemple dans l’expérience de la double fente, où un électron passe par deux fentes en même temps !). Pour en revenir à l’effet tunnel, il existe toujours un chemin qui permet d’aller de l’autre côté du mur. Au plus le chemin est court, au plus la probabilité de l’emprunter est élevée (c’est pourquoi en général on ne peut pas traverser un mur facilement)… Mais la probabilité de choisir un autre chemin que le plus court n’est pas nulle, et donc on peut obtenir un effet tunnel.
  • Quantification : la physique et la mécanique quantique tirent leur nom de cette propriété, qui dit que les valeurs que peuvent prendre certaines mesures sont discontinues. Par exemple, l’énergie d’un atome est forcément multiple d’une certaine constante. Pour l’atome d’hydrogène, on passe de l’énergie de -13.6eV à -3.4eV sans pouvoir prendre de valeur intermédiaire ! Ces paquets permettent de résoudre de nombreux problèmes inexplicables de la fin du XIXème siècle dont celui de l’énergie infinie du corps noir, ou encore d’expliquer les couches d’un atome (les électrons sautent de l’une à l’autre sans pouvoir rester entre)

Les qubits

Maintenant que ces rappels ont été faits et que l’on a le même vocabulaire, on va en revenir à nos ordinateurs quantiques (ordinateurs qui exploitent les propriétés de la mécanique quantique pour fonctionner).

L’unité fondamentale n’est pas le bit (qui vaut 0 ou 1), mais le qubit qui est une superposition d’états.

Par exemple, un qubit est à la fois dans les deux états : il est à 60% « 0 » et à 40% « 1 ». Si on mesure son état exact, il y aura donc 3 chances sur 5 qu’il soit de 0. Grâce à cette superposition d’états, là où 4 bits classiques peuvent valoir l’un des \(2^4 = 16\) états (0000, 0001, 0010, 0011, …) possibles, 4 qubits sont dans ces 16 états en même temps ! Pour trouver un certain état, disons 1111, avec 4 bits il faudra essayer plusieurs combinaisons jusqu’à tomber sur la bonne (au pire 16), tandis que des qubits trouveront 0000 directement.

Les possibilités de calcul avec des qubits sont donc considérables et ils permettent de traiter des problèmes à une vitesse incroyable. Craquer un système de sécurité classique prendrait plus de 10 000 ans avec son ordinateur, tandis qu’un ordinateur quantique mettrait moins de 1 seconde

L’algorithmie

Indépendamment de toutes les problématiques liées aux ordinateurs quantiques (comment stocker de l’information, comment garder les particules dans un état de superposition…) qu’il reste encore à résoudre, de nombreux informaticiens et physiciens ont imaginé des algorithmes dits quantiques qui permettent de résoudre nos problèmes traditionnels via un ordinateur quantique (en une fraction de seconde).

Le plus connu, l’algorithme de Shor, permet de factoriser un nombre entier en ses facteurs premiers. Cette capacité est supposée exponentielle avec un ordinateur classique mais linéaire avec un quantique ! Mais comment peut-on faire, avec des qubits, pour gagner autant de temps ?

Exemple : le problème de Deutsch

Prenons un exemple pratique : vous avez un paquet de 4 cartes, dont deux sont de face rouge et deux sont de face verte. Deux cartes de ces cartes sont placées face cachée devant vous. La première est dévoilée, et vous devez dire si la deuxième est de la même couleur ou non (vous gagnez si vous devinez correctement).

En mécanique classique, il n’y a aucun moyen de savoir. En mécanique quantique, le Problème de Deutsch qu’on vient de présenter a une solution sûre à 100% !

On a donc trouvé un algorithme quantique permettant de répondre systématiquement juste à la question, en réalisant deux opérations quantiques très précises.

Remarque : de manière plus simple, on fait en sorte que si les 2 cartes sont identiques, notre qubit pointe vers la droite et si elles sont différentes, il pointe vers la gauche. Ensuite, s’il est à gauche on le met vers le haut et s’il est à droite, on le met en bas pour pouvoir obtenir la réponse systématiquement ! Car tant qu’il est à droite, si on essaie de le lire, il vaudra parfois 0 et parfois 1…

Autre exemple plus complexe : l’algorithme de Grover

Voici un autre exemple beaucoup plus complexe où il faut trouver un as parmi 4 as !

Bien évidemment, un algorithme ne peut pas « faire ce qu’il veut », toutes les opérations décrites ci-dessus sont possibles car elles entrent dans le cadre de la mécanique quantique (et de ses formules)…

L’algorithme quantique pour IA qui améliore les temps de calcul

« Pouvoir résoudre un système linéaire est simple pour un algorithme classique, tant que la taille de la matrice de données ne dépasse pas les 10 000 x 10 000 entrées » explique Zhikuan Zhao, l’un des auteurs de l’algorithme quantique dont on va parler. Or, de tels systèmes entrent en jeux dans la majeure partie des phases de calculs d’une intelligence artificielle, tant ils sont simples à écrire, et « directs » à résoudre.

Voici l’équation traditionnelle d’un tel système, que vous reconnaîtrez dans l’une de ses deux formes : trouver x tel que \(A \cdot x = b\) où A est une matrice et b un vecteur \(\Longleftrightarrow\)

\(\begin{cases} a_{1,1} \cdot x_1 + a_{1,2} \cdot x_2 + … = b_1 \\ … \end{cases}\)

A titre de comparaison, un algorithme classique résout ce problème (10 000 x 10 000 entrées) en 1 trillion (1000 milliards) d’opérations (un processeur de 2GHz fait 2 milliards de calculs à la seconde), l’algorithme de 2009 en 10 000 opérations et celui-ci en 100 opérations, soit 10 milliards de fois plus rapide !

Fournir un algorithme quantique capable de résoudre un tel problème revient donc à diminuer considérablement les temps de calcul des IA et à augmenter la pertinence de ses propositions, notamment en évitant plus facilement les faux-minimum. L’équipe de l’Université Nationale de Singapour a ainsi présenté ce nouvel algorithme quantique pour résoudre des problèmes de matrices denses

Mais si la version de 2009 avait été testée avec quelques qubits, celle de l’article ne l’a pas encore été : le proof-of-principle, qui revient à tester l’algorithme à toute petite échelle, pourrait bien avoir lieu dans quelques années.

Enfin, Zhao pense que « d’ici 3 à 5 ans, on pourra véritablement utiliser les ordinateurs quantiques qu’ont construit les expérimentalistes pour faire des calculs quantiques avec des applications en intelligence artificielle ». Un délai qui peut paraître court, mais il n’en est rien avec l’annonce toute récente par IBM d’un processeur quantique de 50 qubits !

Crédit de l’image de couverture : Lambert Rosique, sur le stand d’IBM à Viva Technology

1 commentaire