Calculateur quantique

Image manquante
GonioX.jpg



Articles de
science physique quantique
Théorie quantique
Électrodynamique quantique
Mécanique quantique
Théorie des champs
Modèle standard
Statistique quantique
Statistique de Bose-Einstein
Statistique de Fermi-Dirac
Statistique de Boltzmann
Auteurs
Bohr ─ de Broglie
Bose ─ Einstein
Fermi ─ Dirac
Heisenberg ─ Pauli
Schrödinger ─ Feynman
Expériences
Formulaire


Un calculateur quantique (computer ne signifie pas ici « ordinateur ») opère ses calculs grâce à la superposition d'états quantiques. De petits calculateurs quantiques ont déjà été construits dans les années 1990 et des progrès sont en cours. Beaucoup de gouvernements et organisations militaires telles que l'OTAN sponsorisent des universités et des centres de recherches pour développer un tel dispositif de calcul à des fins cryptographiques et de surveillance, pouvant servir par exemple au renseignement militaire.

Sommaire
1 Enjeux
2 Idée de base
3 Historique
4 Questions fréquemment posées
5 Structure des calculateurs quantiques

5.1 Principe
5.2 Implémentation

6 Puissance des calculateurs quantiques

6.1 Exemple d'usage en cassage de code

7 Comment ils fonctionnent
8 Comment on les programme dès maintenant
9 Calculateurs solides
10 Avenir commercial ?
11 Quelques références

Enjeux

Si de grands (plus de 256 qubits) calculateurs quantiques peuvent être construits — ce qui n'est pas assuré — ils seront capables de résoudre des problèmes de décryptage et d'accès à l'information plus vite par construction que tout ordinateur classique. Les calculateurs quantiques font appel à des techniques de calcul totalement différentes (cela dit, bien entendu, les transistors des ordinateurs classiques, et même leur afficheurs LCD et imprimantes à laser, exploitent déjà des effets quantiques dans leur fonctionnement, mais pas la superposition d'états).

Idée de base

Chaque fois que l'on ajoute un qubit à un calculateur quantique, sa puissance théorique double. D'après David Deutsch, un ordinateur de 100 qubits permettrait de simuler le fonctionnement de tout un cerveau humain, et un de 300 qubits l'évolution de l'univers entier depuis le Big Bang. Les ordinateurs quantiques courants actuels n'ont pour le moment que 7 qubits, et on pense que pour un nombre plus grand il va falloir passer à des molécules totalement différentes. Les ordinateurs à 7 qubits actuels sont bâtis autour de molécules de chloroforme et leur durée de vie utile ne dépasse pas quelques minutes. On parle par dérision de wetware (il existe des calculateurs à 5 qubits à base solide).

Le professeur Roger Penrose, arguant la présence dans les cellules cérébrales d'éléments nommés microtubules où pourraient peut-être se produire des phénomènes de résonance quantique, a émis l'hypothèse que le cerveau utiliserait ce type de calcul (parallèle ou plus exactement simultané), établissant ainsi selon lui sa différence essentielle avec une machine de Von Neumann (intrinsèquement séquentielle). Il ne s'agit pour l'instant que d'une hypothèse qui lui est propre.

Historique

Dans les années 70 et 80, les premiers ordinateurs quantiques naissent par retournement dans l'esprit de physiciens tels que Richard Feynman, Paul Benioff, David Deutsch ou Charles Bennett. L'idée de Feynman était « Au lieu de nous plaindre que la simulation des phénomènes quantiques demande des puissances énormes à nos ordinateurs actuels, utilisons la puissance de calcul des phénomènes quantiques pour faire plus puissant que nos ordinateurs actuels ».

Longtemps les physiciens ont douté que les calculateurs quantiques utilisables puissent exister, et même qu'on puisse en faire quelque chose de viable s'ils existaient. Mais :

Depuis cette date, toutefois, on ne voit plus arriver beaucoup d'annonces, sans pouvoir dire si cela provient d'un plafonnement dans les recherches ou d'une éventuelle classification en top secret des nouveaux résultats.

Questions fréquemment posées

« Je croyais que dans la mécanique quantique tout était hasard. Comment exploiter cela pour faire des calculs déterministes ? »

En fait et contrairement à une opinion tenace chez les non-physiciens (et même chez certains étudiants en physique en dessous du niveau maîtrise), la mécanique quantique elle-même ne comporte aucune composante aléatoire : les calculs de fonctions d'onde sont tout ce qu'il y a de plus déterministes, bien qu'ils soient très complexes à effectuer. La source d'aléa n'est pas dans la mécanique sous-jacente, mais dans l'acte d'observation lui-même, c'est-à-dire la mesure (autrement dit pas dans la réalité, mais dans ce que nous en observons. Voir Hugh Everett).

La réponse s'en déduit : sera utilisable pour un calcul déterministe tout processus quantique dont le résultat sera le même quelle que soit la mesure effectuée. L'art de la programmation quantique consiste à forcer à coups de transformations successives (qui doivent toutes être réversibles!) la fonction d'onde dans de telles configurations. Cela ne nécessite pas de connaissances en physique (pas plus que la programmation ne demande de connaissances en électronique), mais il est en revanche indispensable de très bien maîtriser l'algèbre linéaire : matrice, diagonalisation, triangulation, valeur propre, vecteur propre, etc.

Structure des calculateurs quantiques

Principe

En mécanique quantique, il est possible pour une particule d'être virtuellement en deux endroits à la fois, ou en deux états à la fois. C'est comme le chat de Schrödinger : il est pour l'observateur à la fois mort et vivant en même temps (de son point de vue, en revanche, le chat ne peut s'observer lui-même que vivant). Cette possibilité d'être dans de multiples états simultanément, en attente d'une observation, est appelée superposition.

La mémoire d'un ordinateur classique est faite de bits. Chaque bit porte soit un 1 soit un 0. La machine calcule en manipulant ces bits. Un calculateur quantique travaille sur un jeu de qubits. Un qubit peut porter soit un un, soit un zéro, soit une superposition d'un un et d'un zéro (ou, plus exactement, il porte une distribution de phase, angle qui pour 0° lui fait prendre la valeur 1, pour 90° la valeur 0, et entre les deux la superposition d'états dans les proportions du sin² et du cos² de la phase). Le calculateur quantique calcule en manipulant ces distributions.

Interroger un qubit dont la phase p n'est pas de 0° ou de 90° ne sert pas à grand-chose : on obtiendra la réponse 0 avec la probabilité sin²p, et la réponse 1 avec la probabilité cos²p... et il est possible de construire des générateurs aléatoires bien moins onéreux! En revanche, si on arrive à créer un algorithme qui le conduit systématiquement à une phase 0° ou 90°, on obtiendra un résultat déterministe. Encore faut-il que celui-ci corresponde à une réponse cherchée.

On remarquera que le problème n'est pas dénué de similitude avec la célèbre énigme où il faut obtenir une réponse juste de deux gardiens dont l'un dit toujours la vérité et l'autre ment toujours sans qu'on sache lequel est lequel : il faut combiner les incertitudes de façon à très précisément les annuler.

Implémentation

Un calculateur quantique pourrait être implémenté à partir de toute particule pouvant avoir deux états à la fois excités et non excités au même moment. Ils peuvent être construits à partir de photons « présents » à deux endroits au même moment, ou à partir de protons et de neutrons ayant un spin positif, négatif ou les deux en même temps tant qu'ils ne sont pas observés.

Une molécule microscopique pouvant contenir plusieurs millions de protons et de neutrons. On pourrait imaginer de les utiliser comme ordinateurs quantiques avec plusieurs millions de qubits, mais le calcul quantique exige du système qui le porte deux contraintes fortes pour être utilisable :

David Deutsch émet l'idée suivante : si l'univers entier est simulable dans ses moindres détails avec un ordinateur de 300 qubits, comme le suggère le calcul, cela signifie :

Deutsch penche pour cette seconde hypothèse. Tout cela est évidemment très controversé.

Puissance des calculateurs quantiques

Il peut être très difficile de trouver tous les facteurs premiers d'un grand nombre (par exemple de 1000 chiffres). Ce problème de factorisation est difficile pour un ordinateur ordinaire à cause de l'explosion combinatoire. Un calculateur quantique pourrait résoudre ce problème en un temps linéaire : si un nombre est représenté par n bits (c'est-à-dire long de n chiffres binaires), alors un ordinateur quantique avec plus de 2n qubits peut trouver ses facteurs. Il peut aussi résoudre un problème connexe, celui du logarithme discret.

Cette capacité permettrait à un ordinateur quantique de casser une bonne partie des systèmes cryptographiques actuellement utilisés, en particulier la plupart des méthodes de chiffrement asymétriques : RSA, ElGamal ou Diffie-Hellman. Ces algorithmes sont utilisés pour protéger des pages Web, des messages électroniques, et beaucoup d'autres types de données. Parvenir à passer ces protections serait un avantage majeur pour l'organisation ou le pays qui y parviendrait.

La seule façon de rendre sûr un algorithme tel que RSA deviendrait d'augmenter la taille de la clé (et donc la lenteur du codage) jusqu'à ce qu'elle soit plus grande que le plus grand des ordinateurs quantiques jamais construits. Or la taille des moyens de calcul dont dispose par exemple la National Security Agency ne sera évidemment jamais rendue publique. La conséquence en est que les pays ou organismes voulant se protéger verront augmenter de plusieurs ordres de grandeur le coût et le délai de leurs communications, sans jamais être certains pour autant que cela sert à quelque chose. Si le RSA peut donc être rendu sûr, ce sera malheureusement au prix d'une lourde réorganisation des communications d'entreprise, de leur coût, et de leur commodité.

Un calculateur quantique pourrait être à la fois trop petit pour être vu et factoriser des entiers comportant quelques dizaines de milliers de bits. Un ordinateur classique utilisant les algorithmes connus pourrait aussi les factoriser, mais se heurterait à l'explosion combinatoire. Si l'on voulait un résultat avant que le soleil ne s'éteigne, peut-être faudrait-il donner à cet ordinateur un degré de parallélisme le rendant plus grand que l'univers connu, ce qui rendrait problématique sa construction.

Bien entendu (c'est tout de même la raison pour laquelle on les avait imaginés au départ), les calculateurs quantiques pourraient être utilisés... pour des simulations de mécanique quantique. L'accélération pourrait être aussi grande qu'avec la factorisation. Ce serait d'un grand bénéfice pratique pour beaucoup de physiciens, car les calculs quantiques deviennent extrêmement complexes dès qu'on sort de quelques cas triviaux.

Le calculateur quantique a donc un avantage sur les ordinateurs classiques dans trois types d'applications :

Un quatrième avantage, bien que plus petit, a été découvert plus récemment : la recherche quantique rapide dans une base de données (en anglais: quantum database search) par l'algorithme de Grover.

Ces usages étant proches de celui de l'informatique classique, on utilise parfois le terme ordinateur quantique pour désigner un calculateur quantique, bien que les composants algorithmiques de ce type de machine théorique soient distincts de l'unité de calcul quantique elle-même.

Exemple d'usage en cassage de code

Supposons qu'il y ait un problème, tel que trouver le mot de passe pour déchiffrer un fichier. Ce problème possède quatre propriétés :

Pour les problèmes possédant ces quatre propriétés, n / 2 essais en moyenne seront nécessaires pour trouver la réponse, en utilisant un ordinateur classique. Le temps nécessaire à un ordinateur quantique pour le résoudre sera proportionnel à la racine carrée de n, ce qui revient à diviser par deux le nombre de chiffres du compte des essais !

Il est tentant d'attaquer ainsi des chiffrement symétriques comme 3DES ou AES. Mais il est également possible de s'en défendre, en doublant « simplement » la longueur de clé (ainsi que la lourdeur et le coût du cryptage).

Il existe aussi une toute autre méthode pour assurer la sûreté des communications : la cryptographie quantique : celle-ci ne protège pas d'une indiscrétion, mais rend en revanche cette dernière immédiatement connue.

Comment ils fonctionnent

Un ordinateur classique ayant trois bits de mémoire peut stocker uniquement trois uns ou zéros digitaux. À un moment donné, il pourrait contenir les bits « 101 ». Un ordinateur quantique ayant trois qubits peut en fait stoker 16 valeurs, assemblées deux par deux pour former 8 nombres complexes. Il pourrait contenir ceci :

État Amplitude Probabilité
(a+\boldsymbol{i}b) (a2 + b2)
000 0.37 + \boldsymbol{i} 0.04 0.14
001 0.11 + \boldsymbol{i} 0.18 0.04
010 0.09 + \boldsymbol{i} 0.31 0.10
011 0.30 + \boldsymbol{i} 0.30 0.18
100 0.35 + \boldsymbol{i} 0.43 0.31
101 0.40 + \boldsymbol{i} 0.01 0.16
110 0.09 + \boldsymbol{i} 0.12 0.02
111 0.15 + \boldsymbol{i} 0.16 0.05

Il y aurait eu n qubits, cette table aurait eu 2n lignes. Pour un n aux alentours de 100, il y aurait eu plus de lignes que d'atomes dans l'univers connu.

La première colonne montre tous les états possibles pour trois bits. Un ordinateur classique peut seulement porter un de ces états à la fois. un ordinateur quantique, lui, peut être dans une superposition de ces 8 états à la fois. La deuxième colonne montre l'amplitude pour chacun des 8 états. Ces 8 nombres complexes sont un instantané du contenu d'un ordinateur quantique à un moment donné. Durant le calcul, ces trois nombres changeront et interagiront les uns avec les autres. En ce sens, un ordinateur quantique à trois qubits a bien plus de mémoire qu'un ordinateur classique à trois bits.

Cependant, il n'est pas possible de voir directement ces trois nombres. Quand l'algorithme est fini, une seule mesure est accomplie. La mesure retourne une simple chaîne (string) de 3 bits et efface les 8 nombres quantiques. La chaîne de retour est générée aléatoirement. La troisième colonne donne la probabilité pour chacune des chaînes possibles. Dans cet exemple, il y a 14% de chance que la chaîne retournée soit « 000 », 4% que ce soit « 001 », ainsi de suite. Chaque nombre complexe est nommé « ampere » et chaque probabilité une « amplitude carrée », parce qu'elle est égale à |a+b\boldsymbol{i}|^2. La somme des huit probabilités est égale à un.

Typiquement, un algorithme d'un ordinateur quantique initialisera tous les nombres complexes à des valeurs égales, donc tous les états auront les même probabilités. La liste des nombres complexes peut être imaginée comme un vecteur à 8 éléments. À chaque étape de l'algorithme, le vecteur est modifié par son produit avec une matrice. La matrice provient de la physique de la machine et sera toujours inversible, et s'assurera que les probabilités continuent à être égales à un.

Comment on les programme dès maintenant

Il faut d'abord réaliser un calcul conduisant à un état non-superposé. En effet, si on interroge un qubit qui se trouve dans une superposition d'états, la réponse sera aléatoire et ne nous apprendra pas grand-chose. Il faut donc trouver un algorithme donnant une réponse unique pour tous les chemins de calcul possibles. C'est un problème semblable à celui des énigmes où l'on doit obtenir une réponse toujours vraie en la posant à une série d'intermédiaires dont on sait que certains mentent toujours et d'autres jamais. La question est donc de trouver un calcul parvenant à cet invariant, par exemple dans le cas du cassage d'un code la clé de chiffrage que l'on cherche à déterminer.

Un autre problème ensuite est de le mesurer : la lecture d'un seul bit d'un état quantique détruit la totalité de cet état. Il faudra donc refaire le calcul autant de fois que la réponse souhaitée comporte de bits, mais le temps correspondant sera juste proportionnel à ce nombre de bits et non exponentiellement plus grand, ce qui est justement le but recherché.

Damian Conway a créé pour le langage Perl un module nommé Quantum::Superpositions qui permet de simuler (en faisant de l'algorithmique ordinaire en coulisses, bien sûr) le fonctionnement d'un périphérique de calcul quantique. Ce module est très utile pour écrire et tester des programmes à échelle minuscule (sur des clés à quatre bits, par exemple); les programmes réalisés seront intégralement utilisables sur un périphérique de calcul quantique (s'il en existe un jour) en remplaçant les appels au module par les appels correspondant à ce périphérique, sans rien toucher au programme perl lui-même. On pourra alors allégrement craquer en principe des clés de 384 bits et plus en un temps comparable.

L'expression d'un calcul de primalité : 

 sub is_prime {
           my ($n) = @_;
           return $n % all(2..sqrt($n)+1) != 0
         }

n'est pas sans rappeler l'écriture en langage APL, qui lui aussi traite globalement les tableaux, ou d'un langage fonctionnel comme Haskell.

Calculateurs solides

Des recherches sont également entreprises pour chercher à réaliser un ordinateur quantique à base solide, comme le sont nos microprocesseurs actuels.

Avenir commercial ?

Même si les problèmes techniques posés par la réalisation de calculateurs quantiques sont résolus à terme, leur avenir commercial immédiat ne semble pas se situer dans le grand public. En dehors des algorithmes de Shor pour le cassage de code et de Grover pour la recherche efficace dans des bases de données, plus une nombreuse classe de calculs de physique théorique, ainsi peut-être que de simulation numérique, on connaît pour le moment peu de services qu'une carte de calcul quantique insérée dans un PC pourrait rendre au particulier. On ne voit pas par exemple quel parti pourrait en tirer un traitement de texte ou un navigateur Internet.

En évitant de rééditer quelques erreurs historiques célèbres, bornons-nous à constater que l'avenir reste ouvert en ce qui concerne le calcul quantique chez les particuliers.

Quelques références


Image manquante
Symbole-ordinateur.png


Portail Informatique - Accédez d'un seul coup d’œil à toute la série des articles de Wikipédia concernant l'informatique.

See also: Calculateur quantique, 1994, 1996, 1998, 1999, 19 décembre