Ordinateur quantique
Un ordinateur quantique opère ses calculs grà¢ce à la superposition quantique d'états quantiques. De petits ordinateurs quantiques ont déjà été récemment construits 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 ordinateur à des fins cryptographiques et de surveillance, pouvant servir par exemple au renseignement militaire.
Il est largement suspecté que si de grands ordinateurs quantiques pouvaient être construits, ils seraient capables de résoudre certains problèmes plus vite qu'aucun ordinateur classique. Les ordinateurs quantiques sont différents de ceux-ci, même si ces derniers utilisent des effets quantiques autre que la superposition d'états.
Chaque fois que l'on ajoute un qubit à un ordinateur 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. Revenons sur Terre en 2004 : les ordinateurs quantiques courants actuels n'ont pour le moment que 7 qubits, et on pressent 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.
| Sommaire |
|
2 Structure des ordinateurs quantiques 3 Puissance des ordinateurs quantiques 4 Comment ils fonctionnent 5 Comment on les programme dès maintenant |
Dans les années 70 et 80, les premiers ordinateurs quantique naissent dans l'esprit des 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.
Pendant longtemps les physiciens ont douté que les ordinateurs quantiques puissent exister, et même qu'on puisse en faire quelque chose de viable s'ils existaient. Mais en 1994, Peter Shor, un scientifique de AT&T montre qu'il est possible de factoriser des grands nombres dans un temps raisonnable à l'aide d'un ordinateur quantique. En 1996, Lov Grover, invente un algorithme basé sur les ordinateurs quantiques permettant de trouver une entrée dans une base de données non-triée en . Puis, en 1998, IBM est le premier à présenter un ordinateur quantique de 2 qbits. En 1999, l'équipe d'IBM utilise l'algorithme de Grover sur un ordinateur de 3 qbits et battent leur record l'année suivante avec ordinateur de 5 qbits. Le 19 Décembre 2001, IBM crée un ordinateur quantique de 7 qbits et factorise le nombre 15 (!) grace à l'algorithme de Shor.
En mécanique quantique, il est possible pour une particule d'être en deux endroits à la fois, ou en deux états à la fois. C'est comme le chat de Schrà¶dinger : il est à la fois mort et vivant en même temps. Cette possibilité d'être dans de multiples états simultanément est appelée superposition.
La mémoire d'un ordinateur classique est faite de bits. Chaque bit porte soit un un soit un zéro. La machine calcule en manipulant ces bits. Un ordinateur quantique maintient lui un jeu de qubits. Un qubit peut porter soit un un, soit un zero, soit une superposition d'un un et d'un zéro. L'ordinateur quantique calcule en manipulant ces qubits.
Un ordinateur quantique peut être implementé en utilisant n'importe quelle petite particule qui peut avoir deux états. Des ordinateurs quantiques peuvent être construits à partir d'atomes qui sont à la fois excités et non excités au même moment. Ils peuvent être construits à partir de photons de lumière qui sont à deux endroits au même moment. Ils peuvent être construits à partir de protons et de neutrons ayant un spin soit positif soit négatif ou les deux en même temps.
Une molécule microscopique peut contenir plusieurs millions de protons et de neutrons. Elles peuvent être utilisées comme ordinateurs quantiques avec plusieurs millions de qubits.
Il peut être très difficile de trouver tous les facteurs premiers d'un grand nombre. Ce problème de factorisation passe pour difficile pour un ordinateur ordinaire. Un ordinateur quantique pourrait résoudre ce problème très rapidement. Si un nombre est représenté par n bits (s'il est 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 beaucoup de systèmes cryptographiques actuellement utilisés. La plupart des méthodes de chiffrement asymétriques couramment utilisées pourraient être cassées en peu de temps : 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 celui qui y parviendrait. La seule façon de rendre sà»r un algorithme tel que RSA serait d'augmenter la taille de la clé jusqu'à ce qu'elle soit plus grande que le plus grand des ordinateurs quantiques jamais construits. Il semble probable qu'il sera toujours possible de créer des ordinateurs classiques ayant plus de bits que le plus grand des ordinateurs quantiques, et donc de produire de telles clés. Si cela se révèle exact, RSA pourra être rendu sà»r.
Si un ordinateur quantique était basé sur les protons et neutrons d'une molécule, il serait trop petit pour être vu, mais pourrait factoriser des entiers ayant plusieurs miliers de bits. Un ordinateur classique utilisant les algorithmes connus pourrait aussi les factoriser. Mais pour le faire avant que le soleil s'éteigne, il aurait à être plus grand que l'univers connu. Ce serait quelque peu problématique pour sa construction.
De façon probablement pas si surprenante, les ordinateurs 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.
L'ordinateur quantique est donc reconnu pour avoir un gros avantage sur les ordinateurs classiques dans trois types d'applications : la factorisation en nombres premiers, le logarithme discret et les simulations de physique quantique. Cependant, il n'y a pas de preuves que l'avantage soit réel : un algorithme classique tout aussi rapide pourrait être découvert, bien que cela semble improbable. Il y a aussi un autre problème o๠les ordinateurs quantiques ont un avantage, bien que plus petit (quadratique). C'est la recherche quantique dans une base de données (en anglais: quantum database search).
Dans ce cas l'avantage est prouvable. Cela établit de manière certaine que l'ordinateur quantique idéal est supérieur aux ordinateurs classiques.
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 :
Il n'y a actuellement pas d'autres problèmes connus pour être bien plus facilement solvables par un ordinateur quantique. Cependant, les recherches se poursuivent, et d'autres problèmes à résoudre pourraient être identifiés.
Il y aurait eu qubits, cette table aurait eu lignes. Pour un aux alentours de 100, il y aurait eu plus de lignes que d'atomes dans l'univers.
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 à . 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. A 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.
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๠il 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 128 bits et plus.
Le module écrit originellement par Damian Conway : http://search.cpan.org/~dconway/Quantum-Superpositions-1.03/lib/Quantum/Superpositions.pm
Le site d'IBM sur le calcul quantique :
http://www.research.ibm.com/resources/news/20011219_quantum.shtml
Calcul quantique à Stanford :
http://squint.stanford.edu/qc/links.htmlHistorique
Structure des ordinateurs quantiques
Puissance des ordinateurs quantiques
Pour les problèmes possèdant ces quatre propriétés, 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 . C'est une forte augmentation de vitesse, réduisant le temps de résolution de certains problèmes à quelques secondes au lieu de quelques années. Il pourrait être utilisé pour attaquer des algorithmes de chiffrement symétrique comme 3DES ou AES. Mais il est également facile de s'en défendre, en doublant simplement la longueur de clé. Il y a également d'autres méthodes pour une communication sà»re, comme l'utilisation de la cryptographie quantique.Comment ils fonctionnent
Un ordinateur classique ayant trois bits de mémoire peut stocker uniquement trois uns ou zéros digitaux. A 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é
000
001
010
011
100
101
110
111
Comment on les programme dès maintenant
