FLASH INFORMATIQUE FI



L’ordinateur quantique, douze années après Shor




Valerio SCARANI


NdR : Le 6 avril, lors de la la conférence organisée par les Irrotationnels (irrotationnels.epfl.ch), l’ampli SG1 de l’EPFL était plein pour écouter Valerio Scarani parler de l’ordinateur quantique. Public essentiellement étudiant venu des sections de physique et d’informatique, car l’ordinateur quantique se situe à la rencontre de ces deux mondes. Fantasme ou future réalité, l’avenir nous le dira, mais les expériences sont passionnantes ; avec Valerio Scarani tout le monde, ou presque peut comprendre ce qui se cache derrière l’intrication !

JPEG - 4.3 ko
Le circuit qui permet de réaliser un calcul quantique ressemble à un circuit classique. La grande différence entre la physique quantique et la physique classique réside dans les états du système, en particulier dans la possibilité de réaliser un état intriqué de plusieurs sous-systèmes (représenté ici par le nuage gris et l’état psi ; voir texte pour l’explication).

Le danger vient de la physique

La découverte d’un algorithme permettant de factoriser les nombres entiers avec une complexité polynomiale ne pouvait que déclencher un grand intérêt, en raison notamment du danger qu’un tel algorithme constitue pour les méthodes de cryptage à clé publique. Mais en 1994, quand Peter Shor annonça sa découverte, les gens virent rapidement qu’il ne fallait pas courir bloquer toutes les transactions sur internet : il fallait plutôt courir au département de physique. Car l’algorithme de Shor fonctionne sous l’hypothèse qu’une étape de la factorisation (la recherche de la période d’une fonction) est effectuée avec des systèmes qui obéissent aux lois de la physique quantique. Un nombre de plus en plus grand de départements de physique, en effet, a relevé le défi de réaliser un calcul quantique (ou, de manière plus médiatique, de construire un ordinateur quantique). Quelques étapes importantes ont été franchies, mais le défi est toujours ouvert.
Cet article est écrit par un physicien et s’adresse en premier à une communauté de sciences de l’information. Ces destinataires savent ce qu’est un calcul : input - portes logiques - output. Je vais alors me concentrer sur l’autre aspect de la question : qu’est-ce qu’un système physique quantique ? Pourquoi est-il différent de coder l’information dans ces systèmes, plutôt que dans des systèmes classiques ?

Information et physique

Le célèbre mot de Rolf Landauer, Information is physical, est l’une de ces lapalissades géniales qui clarifie le regard que les scientifiques portent sur leur propre activité. Toute information est codée dans des systèmes physiques - et où ailleurs voudriez-vous la coder ? Il semble dès lors que, pour le codage et le traitement de l’information, il reste à chercher le système physique le plus efficace pour une tâche donnée. Pour une initiation des jeunes au codage, des bouts de bois orientés différemment réalisent une liste de bits de manière très pédagogiques. Dans un CD, la valeur du bit est codée dans la profondeur du sillon. Les disques durs se basent sur l’aimantation de petits domaines magnétiques.
Pour s’approcher de l’ordinateur quantique, il faut commencer par réaliser que tous les systèmes physiques qu’on vient de mentionner (bâtonnets, hauteurs, aimantations) codent l’information de la même manière. Les différences, énormes, entre ces exemples, se situent au niveau de l’efficacité, de la rapidité, de la densité - mais c’est dans tous les cas un codage de l’information dans des systèmes classiques. Or, depuis un siècle environ, les physiciens ont découvert qu’il existe une physique différente de celle qui gouverne la vie de tous les jours. Pour des raisons historiques, on l’a appelée physique quantique : il est bien connu qu’elle sert notamment à la description des systèmes microscopiques. Le mot description est ici important : c’est dans la description des propriétés d’un système physique (son état) que la physique quantique se différencie de la physique classique.

Flèches classiques et flèches quantiques

Dans ce paragraphe, je vais essayer de donner une idée de comment on décrit un système en physique quantique, en comparaison avec la description classique qui suit la perception de la vie de tous les jours. Mon système physique, d’abord classique et ensuite quantique, sera une flèche. C’est un système dont les propriétés se réduisent à pointer dans une direction : ce système est donc plus simple que le célèbre point matériel de la mécanique, dont la liste des propriétés est beaucoup plus longue : tout ce que vous pourriez demander au sujet de la position et de la vitesse du point. En physique, on appelle état l’ensemble des propriétés que le système possède à un moment donné.
Dans la vie de tous les jours, si une flèche pointe dans une direction donnée (propriété bien définie, c’est-à-dire état pur), elle pointe dans cette direction avec certitude, et toutes les autres directions sont exclues avec autant de certitude. Les propriétés d’une flèche quantique ont une structure plus riche : avec certitude, la flèche pointe dans une direction donnée et ne pointe pas dans la direction opposée . Pour toutes les directions intermédiaires cependant, il n’y a pas de propriété certaine : si on pose la question « est-ce que la flèche pointe dans cette direction-ci ? » on peut obtenir les deux réponses, oui et non, chacune avec une probabilité bien définie (comme on s’y attend, plus la direction qu’on regarde est proche de celle définie par l’état, plus la probabilité de réponse positive est grande).
Qu’est-ce que cela a à voir avec l’information ? Supposons que flèche vers le haut code le bit 0, flèche vers le bas code le bit 1. L’aimantation dans les disques durs code l’information précisément de cette manière. Dans un codage classique (comme dans les disques durs), l’état flèche vers la droite n’a aucun lien avec les deux états du codage, car si la flèche pointe vers la droite, elle ne pointe sûrement ni vers le haut ni vers le bas ; on pourrait éventuellement utiliser ce troisième état pour coder la valeur 2 et réaliser donc un trit. En somme, un bit classique est associé à deux états physiques séparés par une infinité d’états intermédiaires qui ne jouent aucun rôle. Un bit quantique (qubit) au contraire peut assumer une infinité d’états (toutes les rotations de la flèche) ; mais un état donné est discernable avec certitude seulement d’un autre (celui dans lequel la flèche pointe dans la direction opposée).
Le lecteur est probablement en train de se dire que, si le codage quantique se réduisait à utiliser toutes les directions d’une flèche, on pourrait le simuler en utilisant les flèches classiques. En effet, cela n’est pas tout : la nature devient plus riche et étonnante encore lorsque l’on considère des systèmes composés, c’est-à-dire dans notre cas plusieurs flèches. Il est absolument naturel de considérer des systèmes composés comme porteurs d’information : on veut travailler sur plusieurs bits, pas sur un seul. Pour des raisons de brièveté, je me limiterai à un exemple avec deux seules flèches. En physique classique, l’état les deux flèches sont opposées (état pur du système composé, c’est-à-dire propriété bien définie décrivant la relation entre les deux flèches) signifie que la première flèche pointe dans une certaine direction (état pur), la deuxième dans une autre (état pur), et il se trouve que ces deux directions sont l’opposée l’une de l’autre. En physique quantique on peut définir le même état pur pour le système composé, sans que cela ne corresponde à des états purs des flèches prises séparément : en d’autres termes, on peut encoder une relation pure. Cela est très étonnant : c’est le phénomène de l’intrication (entanglement) qui a profondément gêné Einstein, Schrödinger et bien d’autres - mais qui, que cela nous plaise ou non, existe, ayant été mis en évidence dans un nombre incalculable d’expériences depuis au moins vingt ans.

Retour aux algorithmes

Pourquoi est-ce que la description quantique aide à factoriser les nombres entiers ? Le coeur de la réponse est l’intrication. On a dit que la physique quantique permet de réaliser des états qui décrivent des pures relations. Or, supposons que dans un algorithme la valeur de certains bits ne soit pas vraiment utilisée, car ce qui compte est seulement leur relation (par exemple, leur XOR, ou la distance de Hamming par rapport à une suite de référence). Dans ce cas, le codage dans des bits classiques nous force à travailler avec une suite particulière de bits qui (parmi bien d’autres propriétés qu’on n’utilisera jamais) réalise celle qui nous intéresse. Si l’information est codée dans des qubits en revanche, il est possible de préparer l’état qui correspond à la relation qui nous intéresse pure, sans autre structure. Voilà qui suggère que, dans certains algorithmes, le nombre de ressources à utiliser ou d’opérations à effectuer va être réduit en utilisant le codage quantique plutôt que le codage classique. Une métaphore qui traduit la même idée est celle du parallélisme quantique : l’intrication permet de tester toutes les suites de bits à la fois, alors que classiquement on ne peut entrer qu’une liste de bits à la fois dans une fonction de calcul.
Certes, cette explication n’est que faiblement convaincante. Si quelqu’un veut en savoir plus, je ne peux malheureusement que le renvoyer à l’étude détaillée du calcul de Shor : de nos jours, personne n’a encore trouvé une présentation à la fois simple et exacte du pouvoir de l’ordinateur quantique. En d’autres termes, personne ne sait vraiment pourquoi l’algorithme de Shor marche. Personne ne sait d’ailleurs non plus pourquoi depuis 1994 on a trouvé très peu d’autres algorithmes que celui-ci pour lesquels le codage quantique s’avère meilleur - essentiellement, la généralisation de l’algorithme de factorisation à tous les hidden subgroup problems, et l’algorithme de Grover qui permettrait d’accélérer la recherche dans une liste non structurée (trouver un nom dans un annuaire téléphonique sans ordre alphabétique).

Défis et espoirs

L’ordinateur quantique le plus performant réalisé jusqu’à présent comportait 7 qubits, et il a permis de factoriser le nombre 15 : le cryptage RSA a encore de beaux jours devant lui ! La raison n’est ni le manque d’effort expérimental, ni le manque de moyens financiers : simplement, le contrôle de N systèmes quantiques un par un ou deux par deux (les portes logiques single-qubit et two-qubit) est un défi majeur. Par exemple, le principe physique selon lequel le calcul quantique avec 7 qubits a été effectué, c’est-à-dire la résonance magnétique nucléaire, ne permet pas d’envisager une extension à plus grande échelle (à plus de qubits) : cela fut juste une prouesse expérimentale de physiciens, une preuve de principe que les lois de la physique quantique s’appliquent (chose dont personne ne doute vraiment), une pierre milliaire sur une route qui ne continue pas. D’autres techniques sont plus prometteuses : les ions piégés, les atomes dans des réseaux optiques... Et les semiconducteurs, qui sont à la base des ordinateurs classiques ? Pour l’instant, ils constituent la déception du domaine : en dépit des efforts des meilleurs groupes expérimentaux et des nombreuses idées des théoriciens, personne n’est encore arrivé à contrôler l’intrication dans ces systèmes (d’autant plus étonnant que le contrôle des systèmes individuels, la rotation des flèches, a atteint une précision remarquable).
On aurait bien des raisons d’être prudents, voire sceptiques devant le futur de l’ordinateur quantique : verra-t-il le jour ? Si oui, servira-t-il à quelque chose, mis à part le craquage du RSA qui entre-temps, avec un peu de chance, aura été remplacé par autre chose ? A cette attitude prudente, légitime et peut-être même sage, j’ose préférer l’enthousiasme de certains visionnaires : oui, l’ordinateur quantique verra le jour, et d’ici-là nous aurons appris encore beaucoup sur la physique, sur les sciences de l’information, et sur cette région à peine explorée qui s’étend entre les deux !

Lectures conseillées

Pour une présentation sans équations de la physique quantique : Valerio Scarani, Quantum Physics : A First Encounter (Oxford University Press, Oxford, 2006) [Traduction mise à jour de : Initiation à la physique quantique (Vuibert, Paris, 2003)].
Pour approfondir le calcul quantique, avec le formalisme : Michel Le Bellac, Introduction à l’information quantique (Belin, Paris, 2005).



Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.