Calculateur quantique

Un calculateur quantique (parfois appelé ordinateur quantique à cause d'une traduction malheureuse de l'expression quantum computer) opère ses calculs grâce, entre autre, à 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. C'est un domaine en plein essor soutenu financièrement par de nombreuses organisations, entreprises ou gouvernements, du fait de l'importance de l'enjeu : gagner plusieurs ordres de grandeur en calcul, avec une puissance et des opérations peu imaginables à l'aide d'un ordinateur classique. Ce dernier calcule en effet avec un degré de parallélisme limité (même si grand; voir par exemple Blue Gene) et de façon séquentielle. La difficulté actuelle majeure concerne la réalisation physique de l'élément de base de l'ordinateur quantique : le qubit. Le phénomène de décohérence, c'est à dire de perte des effets quantiques sur le long terme, est le principal frein au développement du calculateur quantique.

Sommaire

1 Enjeux
2 Historique
3 Réalisations physiques
4 Structure des calculateurs quantiques
- 4.1 Principe
- 4.2 Implémentation
5 Intérêts des calculateurs quantiques
- 5.1 Exemple d'usage en cassage de code
6 Comment fonctionnent-ils ?
7 Comment les programme-t-on dès maintenant ?
8 Avenir commercial
9 Discussions autours du calculateur quantique
10 Liens externes

[modifier] 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 que tout ordinateur classique. Les calculateurs quantiques font appel à des techniques de calcul totalement différentes de celles habituellement connues. Ils se basent sur des propriétés quantiques de la matière. De nombreux systèmes (transistors des ordinateurs classiques, afficheurs LCD, imprimantes à laser...) exploitent déjà des effets quantiques dans leur fonctionnement, mais ils utilisent des bits classiques en opposition aux qubits (bits quantiques) utilisés en informatique quantique. Des algorithmes s'appuyant sur les caractéristiques des calculateurs quantiques pour décrypter des données protégées par le très courant code RSA existent déjà. L'ordinateur quantique est donc un enjeux majeur dans la sécurité des communications, et donc de l'économie et des états. Des moyens de cryptage quantique qui sont supposés se substituer au RSA dans l'hypothèse de la création effective d'un calculateur quantique sont déjà disponibles dans le commerce. Ils nécessitent cependant une mise en place plus complexe.

[modifier] 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 :

en 1994, Peter Shor, chercheur chez AT&T, montre qu'il est possible de factoriser des grands nombres dans un temps raisonnable à l'aide d'un calculateur quantique. Cette découverte débloque brusquement des crédits ;
en 1996, Lov Grover, invente un algorithme basé sur les calculateurs quantiques permettant de trouver une entrée dans une base de données non-triée en $O(\sqrt{N})$ (Voir Complexité algorithmique) ;
en 1998, IBM est le premier à présenter un calculateur quantique de 2 qubits ;
en 1999, l'équipe d'IBM utilise l'algorithme de Grover sur un calculateur de 3 qubits et battent leur record l'année suivante avec un ordinateur de 5 qubits ;
le 19 décembre 2001, IBM crée un calculateur quantique de 7 qubits et factorise le nombre 15 grâce à l'algorithme de Shor.
en août 2006, le professeur Seth Lloyd, du MIT, annonce dans sa revue Technology review que des calcultateurs à 12 qubits existent dans les laboratoires et qu'il les utilise.

[modifier] Réalisations physiques

De nombreux projets sont en cours à travers le monde pour construire concrêtement des qubits viables et les réunir dans un circuit. Ces recherches mettent en oeuvre de la physique théorique pointue. Les projets suivant semblent avancer à un rythme interressant :

les circuits supraconducteurs avec jonction Josephson. Cette technique est très maléable : il s'agit de dessiner des circuits suffisament résistant à la décohérence. Pour l'instant elle ne permet de coupler qu'au plus deux qubits, mais des recherches sont en cours pour en coupler d'avantage à l'aide d'un résonnateur et d'un SQUID.
Les ions piégés. Cette technique a donné le système possédant le plus de qubits corrélés.
la RMN.
les atomes provenant d'un condensat de Bose-Einstein piégés dans un réseau optique.
les cavités optiques ou micro-ondes résonnantes.
beaucoup d'autres projets plus ou moins avancés.

Certains projets semblent très en phase avec une exploitation industrielle, mais les problèmes de bases restent les mêmes. Des recherches sont ainsi entreprises pour réaliser un ordinateur quantique à base solide, comme le sont nos microprocesseurs actuels. Ces recherches ont entre autres mené l'Université du Michigan à une puce de calcul quantique capable d'être fabriquée en série, sur les lignes de productions existant actuellement qui plus est. Cette puce permet en effet d'isoler un ion et de le faire « léviter » dans un espace confiné, à l'intérieur de la puce.

[modifier] Structure des calculateurs quantiques

[modifier] Principe

Pour comprendre le fonctionnement des calculateur quantique, il faut dépasser la question : « Je croyais que dans la mécanique quantique tout était hasard. Comment exploiter cela pour faire des calculs déterministes ? »

En fait, les calculs de fonction 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 est 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 du calcul quantique consistera à forcer à coups de transformations successives (qui doivent toutes être réversibles!) la fonction d'onde dans de telles configurations.

En mécanique quantique, il est possible pour une particule d'être en deux états à la fois, à la manière du chat de Schrödinger qui est pour l'observateur à la fois mort et vivant en même temps. 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.

Un ordinateur classique ayant trois bits de mémoire peut stocker uniquement trois nombres binaires. À un moment donné, il pourrait contenir les bits « 101 » ou une autre combinaison des 8 possibles (2³). 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)$	$(a 2 + b 2)$
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$

Noter que la somme des probabilités fait bien 1. S'il y avait eu $n$ qubits, cette table aurait eu $2 n$ 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. 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.

[modifier] 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 :

il doit être totalement isolé du monde extérieur pendant la phase calcul, toute observation perturbant le processus. On ne le laisse communiquer à l'extérieur qu'avant (introduction des données) et après (lecture des résultats, ou plus exactement du résultat) ; l'isolement thermique total ne peut exister, mais si l'on arrive à le maintenir le temps du calcul, celui-ci peut avoir lieu sans interférence. Ce phénomène d'interférence est appelé décohérence, c'est le principal obstacle à la réalisation de calculateur quantique. Le temps de décohérence correspond pour un système quantique au temps pendant lequel ses propriétés quantiques ne sont pas corrompues par l'environnement.
il doit se faire sans la moindre perte d'information. En particulier tout circuit de calcul quantique doit être réversible. Dans les circuits logiques "classiques" certaines portes ne vérifient pas cette propriété (porte NAND par exemple). Cependant des astuces de construction permettent de contourner cette difficulté en concervant des informations supplémentaires non directement utiles. Toutes les portes classiques ont un équivalent quantique.

[modifier] Intérêts 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 serait 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.

Les calculateurs quantiques pourraient être utilisés pour des simulations de mécanique quantique. C'est la raison pour laquelle on les avait imaginés au départ. 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 :

la décomposition en produit de facteurs premiers ;
le logarithme discret ;
les simulations de physique quantique.

Un quatrième algorithme 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. Au lieu de parcourir tous les éléments d'une liste pour trouver l'un d'eux qui répond à un critère (par exemple : recherche d'un individu dans le botin en connaissant son numéro de téléphone), cet algorithme utilise des propriétés quantiques pour que cette recherche se fasse plus efficacement.

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.

[modifier] 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 :

La seule façon de le résoudre est de générer des réponses et de les vérifier.
Il n'y a que $n$ réponses possibles à essayer.
Chaque réponse possible prend le même temps à essayer.
Il n'y a pas d'indices au sujet de la meilleure réponse. Générer les réponses aléatoirement est statistiquement aussi rapide que les essayer dans un certain ordre.

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$ ( $\sqrt{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.

Remarque : comme le rappellent les informaticiens, un ordinateur classique comportant p unités de calcul placées en parallèle permettrait de trouver la réponse de cryptographie dans un temps proportionnel à n/p. Autrement dit, le temps de calcul pourrait être inférieur au temps de calcul des ordinateurs quantiques, pour peu que p soit suffisamment grand.

[modifier] Comment fonctionnent-ils ?

[modifier] Comment les programme-t-on 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.

[modifier] 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. Tout dépend évidemment du coût auquel on arrive à les fabriquer. En dehors des algorithmes de Shor pour le cassage de code et de Grover pour la recherche efficace dans des bases de données, ainsi qu'une classe de calculs en physique théorique, quelques applications seraient peut-être envisageables pour des simulations numériques qui butent aujourd'hui sur l'explosion combinatoire.

[modifier] Discussions autours du calculateur quantique

On remarquera que le problème de l'informatique quantique 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.

Chaque fois que l'on ajoute un qubit à un calculateur quantique, le nombre d'états qu'il traite (donc sa puissance théorique, puisque tout se fait en parallèle) 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, ce qui semble créer un paradoxe, qu'il résout d'ailleurs :

soit qu'il existe quelque part une loi inconnue qui nous empêchera d'atteindre cette limite (sans quoi il serait possible à la partie de décrire le tout, ce qui semble curieux)
soit que les univers parallèles au sens d'Hugh Everett existent, et que c'est chez eux qu'est déportée l'immense majorité des calculs, car « le nôtre ne dispose pas à lui seul des ressources suffisantes pour le permettre ».

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, sur une idée du Pr Manniche, 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 reposant sur la taille des tubulines, hypothèse critiquée parce qu'allant à l'encontre des modèles actuels de traitement de l'information par des réseaux de neurones, même si on a récemment découvert une action complémentaire opérée par les cellules gliales.

Le professeur au MIT Seth Lloyd, pionnier du calcul quantique et auteur du livre Hacking the universe mentionne dans le numéro d'août 2006 de la revue Technology Review (page 24) l'existence de calculateurs quantiques a 12 qubits. Il rappelle également qu'il ne faut pas confondre les calculateurs quantiques généraux (destinés a résoudre à terme des problèmes de calcul quelconques) avec d'autres calculateurs quantiques existants spécifiquement concus pour modéliser des phénomenes quantiques, qui constituent pour leur part l'équivalent quantique des anciens calculateurs analogiques.

Il faut toutefois signaler que de nombreux physiciens critiquent l'interprétation des résultats et doutent de la possibilité de construire ces calculateurs quantiques. En effet, si la superposition de plusieurs états quantiques est prévu par la théorie, rien ne permet d'avoir accès à chacun d'eux au moyen d'une mesure. Selon eux, les résultats obtenus avec les calculateurs quantiques actuels ne démontrent rien et n'ont qu'un intérêt marginal. La polémique reste donc forte sur le sujet.

Quelques pistes envisageables quant à l'utilisation des ordinateurs quantiques:

Intelligence artificielle pour le traitement automatique des langues (TAL) : en utilisant de grosses ressources combinatoires un traitement de texte pourrait-il utiliser une représentation de l'univers associé à un texte et mieux réagir à la sémantique qu'il pourrait en inférer ?

A la limite, les amateurs de jeux vidéo seraient-ils heureux de disposer d'un moteur de gestion de collisions physiques très réaliste ?

Les traders, voire de simples particuliers porteurs d'actions pourraient-ils envisager un nombre considérablement plus grand de simulations ?

De manière générale tous les domaines qui peuvent profiter d'une simulation d'un univers riche peuvent théoriquement bénéficier de processeurs quantiques.

Des questions envisagées dans la littérature sont les suivantes : faut-il construire le modèle sur l'ordinateur « classique » puis le faire évaluer par le calculateur quantique, ou bien faut-il laisser tout le travail au calculateur quantique (qui risque d'être moins rapide pour les tâches traditionnelles) ?