Prix Nobel de Physique 2012 et informatique quantique

Le prix Nobel 2012 de Physique a été conjointement attribué au Français Serge Haroche et à l'Américain David Wineland. Leurs travaux portent sur l'optique quantique et pourraient avoir à moyen ou long terme des répercussions importantes ... en informatique.

Par Frédéric Prost.

Serge Haroche

Le prix Nobel 2012 de Physique a été conjointement attribué au Français Serge Haroche et à l'Américain David Wineland. Leurs travaux portent sur l'optique quantique et pourraient avoir à moyen ou long terme des répercussions importantes... en informatique. En effet, depuis une remarque astucieuse de Richard Feynman (lui même prix Nobel de physique en 1965) on sait qu'utiliser les particularités de la physique quantique pourrait conduire à la conception d'ordinateur calculant exponentiellement plus vite que des ordinateurs classiques. Sur quels principes ces fameux ordinateurs quantiques fonctionnent-t-ils ?

Physique quantique et simulation

Comme c'est souvent le cas dans le domaine de l'informatique tout part d'une remarque, en l'occurrence d'un résultat de recherche, négative. En 1982 dans un article théorique qui pourrait sembler n'intéresser que les physiciens théoriciens, "Simulating physics with computers", Richard Feynman prouve qu'on ne peut pas efficacement simuler un système quantique sur ordinateur.

En informatique la notion "d'efficacité", donc dualement de "non efficacité" ou de "difficulté", est assez théorique mais intuitivement simple à comprendre. La complexité d'un problème se jauge à l'évolution du temps qu'il faut pour le résoudre en fonction de la taille de ses entrées.

Prenons un exemple simple : l'addition de deux nombres. Supposons que vous deviez additionner deux nombres de n chiffres. Le temps que vous allez mettre pour calculer leur somme sera proportionnel à n. En effet si vous utilisez la méthode apprise à l'école vous commencez par additionner les chiffres des unités, puis celui des dizaines (en reportant la retenue s'il y a lieu) etc. jusqu'à arriver au chiffre le plus à gauche. On voit que d'après cette méthode additionner deux nombres de taille 2 x n vous prendra en gros deux fois plus de temps que pour additionner deux nombres de taille n. On dit que la complexité de l'addition est linéaire dans la taille de son entrée.

Si maintenant on considère la multiplication de deux chiffres de taille n. Toujours en utilisant la méthode apprise à l'école on s’aperçoit que le temps mis pour calculer le résultat est proportionnel à n x n. En effet on commence par multiplier le chiffre des unités de l'un avec tous les chiffres de l'autre (avec report éventuel des retenues) puis on recommence avec les dizaines etc. Ensuite il reste à sommer les n chiffres obtenus, mais comme le temps pour ces n additions est négligeable devant le temps pris par les multiplications on simplifie les choses et on dit que la complexité de la multiplication est quadratique (proportionnelle au carré de la taille des entrées). Dans le cas de la multiplication on voit que le temps pour résoudre le calcul va évoluer de manière différente : pour multiplier deux chiffres de taille 2 x n le temps pris sera proportionnel à (2 x n)  x (2 x n) soit  (4 x n^2). Autrement dit on mettra quatre fois plus de temps (au lieu de 2 fois plus dans le cas de l'addition rappelons le).

Un problème est jugé "compliqué" si son temps de résolution est exponentiel en la taille de ses entrées. En effet, supposons que le temps de résolution soit proportionnel à 2^n, le fait que la taille de l'entrée augmente seulement de 1 va doubler le temps d’exécution  Très rapidement, pour des valeurs faibles, il n'est plus possible de calculer la solution : cela prend simplement trop de temps. C'est, entre autre, une des raisons pour lesquelles chercher de manière exhaustive tous les mot de passe possibles pour se connecter sur un système n'est pas une attaque dangereuse, pour peu que le mot de passe soit bien choisi.

Dans son article Richard Feynman montrait que la simulation d'un système quantique à n particules prenait un temps exponentiel en n et n'était donc pas efficacement simulable sur un ordinateur. C'est tout son génie que d'avoir vu là une très belle opportunité : s'il n'est pas possible de simuler efficacement un système quantique pourquoi ne pas utiliser un système quantique pour calculer efficacement ce qu'on ne peut pas faire avec des ordinateurs classiques ? L'idée géniale est de coder, ou programmer, en utilisant des particules de telle manière à ce que leur évolution, en suivant les lois de la physique, permettent de simuler un ordinateur qui ferait un nombre exponentiel de calculs en un temps linéaire.

Le chat de Schrödinger et les bits quantiques

L'avènement de la physique quantique dans les années 30 a marqué une véritable révolution intellectuelle, comparable à la relativité d'Einstein, en donnant un modèle de l'infiniment petit parvenant à modéliser des expériences incompréhensibles autrement. Le problème est qu'elle est totalement contre-intuitive (un autre problème étant qu'entre la relativité générale et la physique quantique il y a des contradictions irréfragables qui demeurent : les chercheurs s'évertuent, pour l'instant sans succès, à tenter d'unifier la physique depuis plus de 80 ans maintenant) et mathématiquement complexe.

Une des caractéristiques de base de la mécanique quantique est la superposition des états: il est possible selon la physique quantique que l'état d'une particule soit un mélange de plusieurs états de base.

Pour simplifier si notre système est le résultat d'un tirage au sort par une pièce de monnaie. Ce système a deux états de base, l'un qu'on appelle "Pile" et l'autre qu'on appelle "Face". Dans le monde étrange de la physique quantique, il se trouve que sous certaines conditions, un système peut être un mélange des états de base, un peu comme si le résultat du tirage au sort était un mélange de 30% de "Pile" et de 70% de "Face". Et en fait c'est quand on va mesurer l'état (donc regarder le résultat du tirage au sort) que se dernier va se projeter sur, soit "Pile", soit "Face" (avec une probabilité dans notre cas de 30% pour que ce soit "Pile" et 70% que ce soit "Face").

Pour montrer à quel point c'est contre-intuitif Erwin Schrödinger proposa une célèbre expérience de pensée, dite chat de Schrödinger, où un détecteur mettrait en marche un mécanisme tuant un chat si un phénomène physique particulier arrive (par exemple la désintégration d'un atome). Si ce phénomène physique peut se décrire comme une superposition d'état alors la probabilité de mise à feu dépend de la mesure d'un état quantique en superposition. D'un point de vue mathématique tout se passerait comme si le chat se trouvait dans un mélange d'état "chat vivant" et "chat mort" en même temps. Ce qui n'a pas de sens au niveau macroscopique.

C'est en utilisant cette propriété de superposition qu'on peut créer un bit quantique. Dans un ordinateur classique la plus petite unité d'information est un bit : c'est à dire une information qui est soit "0", soit "1" et rien d'autre. Les calculs dans un ordinateur se font donc en codant le "1" par un courant électrique et le "0" par une absence de courant électrique. Il faut ensuite faire passer ce courant dans un circuit électronique qui en sortie va produire soit "0" soit "1" en fonction de ce qui lui a été fourni en entrée.

L'idée de l'informatique quantique est d'utiliser une particule pour représenter une information qui soit plus riche qu'un bit classique et qui soit à la fois "0" et "1". Maintenant imaginez que vous ayez un bit qui soit à la fois "0" et "1" et que vous l'envoyez dans un circuit électronique adapté : en sortie vous allez récupérer à la fois le calcul du circuit pour "0" et pour "1", et cela en une seule utilisation du circuit ! Normalement il faudrait utiliser le circuit une fois pour "0", regarder le résultat, puis utiliser le circuit pour "1" et observer de nouveau le résultat. En utilisant des bits quantiques tout peut être calculé en une seule utilisation ! En fait le résultat sera une superposition de "0" et "1" qu'il faudra mesurer ce qui donnera un résultat statistique en fonction de la superposition calculée.

Une autre propriété quantique, l'intrication, est nécessaire pour accélérer les calculs. Elle est plus complexe à expliquer et nous ne rentrerons pas dans les détails dans cet article. C'est cette propriété qui est à la base du paradoxe EPR qui a toujours fait douter Einstein quant à la fiabilité de la mécanique quantique. Pourtant ce paradoxe a été expérimentalement vérifié depuis.

Factorisation et recherche dans une liste non ordonnée

Le fait de pouvoir utiliser des bits quantiques et de faire des opérations sur ces bits quantiques permet d'obtenir des résultats impossible à reproduire avec des ordinateurs classiques : c'est ce que Feynman avait prouvé dans son article originel. Il existe deux résultats majeurs.

En 1994 Peter Shor a montré qu'on pouvait factoriser les entiers en temps polynômial avec un ordinateur quantique. Le problème de la factorisation consiste, étant donné un chiffre n, à trouver tous les chiffres qui multipliés entre eux font n. Par exemple étant donné 21 il faut trouver 3 et 7. Ce problème semble simple mais sa complexité est en fait exponentielle à la taille du chiffre à factoriser. Il est également très important d'un point de vue pratique car il est à la base de la cryptographie moderne. Quand vous naviguez sur internet sur des sites sécurisés, en utilisant "https", la sécurité de la communication repose sur le fait que factoriser est difficile.

Le second grand résultat d'informatique quantique a été trouvé par Lov Grover en 1996 : le problème auquel il s'attaquait était de rechercher un élément dans une liste non triée et de répondre "oui" si l'élément est dans liste et "non" sinon. En utilisant un ordinateur classique, il n'y a rien de mieux à faire que d'examiner les éléments un par un jusqu'à tomber sur un qui est égal à l'élément recherché, et de répondre "oui" ou arriver à la fin de la liste et de répondre "non". La complexité de ce problème est proportionnelle au nombre d'élément de la liste (en fait si la liste est de taille n en moyenne il faudra un temps proportionnel à n/2). C'est donc un problème simple. Cependant quand vous cherchez à savoir si un gène apparaît dans une chaîne d'ADN, la taille de votre liste est immense. Lov Grover a donnée un méthode quantique dont le temps est proportionnel à la racine carré de n au lieu de n. Cela est extrêmement significatif quand n devient grand.

L'ordinateur quantique

L'informatique quantique semble donc très prometteuse : elle permet des prouesses qui sont impossibles à réaliser si on utilise des ordinateurs classiques. Le seul hic est qu'il n'existe pas d'ordinateur quantique ! En effet pour fonctionner il faut pouvoir manipuler ces fameux bits quantiques qui par définitions sont des objets infinitésimaux, plus petits que des atomes. Pour l'instant IBM a réussi à faire fonctionner l'algorithme de Shor, montrant expérimentalement que l'informatique quantique n'est pas juste un doux rêve de théoricien. Cependant la machine utilisée par IBM ressemble plus à une expérience de physique théorique (avec force lasers et instruments de pointe) qu'à un ordinateur au sens commun du terme. D'ailleurs les ingénieurs d'IBM ont réussi à factoriser... 15 en 3 x 5 car ils n'avaient implantés que 7 bits quantiques en utilisant des techniques de résonance magnétique nucléaire.

Là est tout le défi des prochaines années pour réaliser un ordinateur quantique : comment passer à l'échelle et construire des ordinateurs capables de manipuler des milliers/millions de bits quantiques ? Le travail pour lequel Serge Haroche a reçu le prix Nobel, pourrait conduire à des implantations de bits quantiques plus efficaces, plus stables, plus faciles à manipuler, mais ce n'est que le premier pas d'un long chemin.