View: Calculateur quantique

La Sphère de Bloch est une représentation d’un qubit

Un calculateur quantique ou ordinateur¹ quantique repose sur des propriétés quantiques de la matière : superposition et intrication d'états quantiques.
De petits calculateurs quantiques ont déjà été construits dès les années 1990 et la recherche progresse, bien que lentement, depuis. Ce domaine est soutenu financièrement par plusieurs organisations, entreprises ou gouvernements en raison de l'importance de l'enjeu : au moins un algorithme conçu pour utiliser un circuit quantique, l'algorithme de Shor, rendrait possible de nombreux calculs combinatoires² hors de portée d'un ordinateur classique en l'état actuel des connaissances. La possibilité de casser les méthodes cryptographiques classiques est souvent mise en avant. La difficulté actuelle majeure (depuis 2008) 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 (perte des effets quantiques en passant à l'échelle macroscopique) freine le développement des calculateurs quantiques.

Intérêt des calculateurs quantiques

Selon l'empirique loi de Moore, la taille des transistors approchera celle de l'atome à l'horizon 2020. À cette échelle, les effets quantiques perturbent le fonctionnement des composants électroniques³. Si de grands calculateurs quantiques (plus de 300 qubits) pouvaient être construits — ce qui n'est pas assuré — ils seraient capables, d'après David Deutsch⁴, de simuler le comportement de l’univers lui-même⁵. Ils pourraient également résoudre des problèmes de cryptanalyse en un temps beaucoup plus court qu'un ordinateur classique. Les calculateurs quantiques demandent des techniques de calcul différentes de la programmation, mais utilisant beaucoup l'algèbre linéaire classique.
Des moyens de chiffrement quantique existent également dans le commerce. Ils ne demandent pas de calculateur quantique et demandent une mise en place plus complexe qu’un chiffrement standard, mais rendent toute interception de message immédiatement détectable.
Que des calculateurs quantiques de taille intéressante soient possibles ou non à terme, leur premier avenir commercial ne sera probablement pas dans le grand public : le calcul quantique exige peu d’entrées et peu de sorties. Il ne se prête donc a priori qu'aux calculs dont la complexité réside dans la combinatoire. On trouve ces problèmes dans l’ordonnancement et les autres calculs de recherche opérationnelle, en bio-informatique, et bien entendu en cryptographie. Le faible volume des entrées-sorties par rapport à celui du traitement semble rendre plausible leur usage à distance, à travers le réseau Internet.

Confidentialité des requêtes

Si les transmissions quantiques se généralisent dans l’avenir, elles assureront une confidentialité totale⁶. On ne peut en effet pas réaliser une copie exacte de l'état intriqué d'un qubit : cette règle est connue sous le nom de théorème de non-clonage⁶. Si un nœud intermédiaire essaie de copier une requête quantique, il la perturbera nécessairement⁶. L'émetteur de la requête pourra détecter l'existence éventuelle de cette perturbation⁶.

Algorithmes utilisant des circuits quantiques

Comme indiqué plus haut, la combinatoire constitue le domaine d'application privilégié des futures cartes de calcul quantique, si elles existent un jour.
Ainsi 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 circuit de calcul quantique pourrait résoudre ce problème en un temps polynomial, c’est-à-dire que pour l’ordinateur quantique, la difficulté augmenterait polynomialement au lieu d’augmenter exponentiellement.
Une analogie possible est de se représenter un calculateur quantique comme un processeur SIMD (carte graphique, par exemple) dont le nombre de pipelines serait $2^N$ fois le nombre N de qubits. L’analogie s’arrête là, un calculateur quantique ne pouvant fournir qu’un bit de résultat à la fois (l’état quantique étant détruit par l’observation), après quoi le calcul doit être recommencé pour demander le suivant.
Cette capacité permettrait à un calculateur quantique de casser de nombreux 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 à casser ces protections serait un avantage majeur pour l’organisation ou le pays qui y parviendrait, et une réédition de l’exploit réalisé pour Enigma.
La seule façon de rendre sûr un algorithme tel que RSA est d’augmenter la taille de la clé en fonction de l'évolution des technologies qui permettent de casser des clés toujours de plus en plus longues, ralentissant en même temps le codage des messages sur les réseaux utilisateurs. Cette clé doit être plus grande que le plus grand des circuits de calcul quantique existants. 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 même jamais savoir si cela sert à quelque chose, et au prix d’une lourde réorganisation des communications, de leur coût, et de leur commodité.
Des circuits quantiques sont déjà utilisés pour des simulations de mécanique quantique, fonction pour laquelle Richard Feynman les avait imaginés au départ. Ils y sont très utiles, car les calculs quantiques deviennent complexes dès qu’on sort de quelques cas triviaux.
Un autre algorithme, au gain moins spectaculaire, a été découvert par la suite : 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 celui qui répond le mieux à un critère (par exemple : recherche d’une personne dans l’annuaire pour trouver son numéro de téléphone), cet algorithme utilise des propriétés de superposition pour que la recherche se fasse de façon globale. Les résultats devraient être en $O(\sqrt{N})$ , N étant le nombre de fiches (et O représentant la comparaison asymptotique), soit mieux qu’une base de données classique bien optimisée, sous réserve de disposer d’un registre quantique de taille suffisante pour les calculs.
En résumé, des circuits de calcul quantique apporteraient un plus aux ordinateurs classiques dans quatre types d’applications :

décomposition en produit de facteurs premiers ;
calcul de logarithme discret ;
simulations de physique quantique ;
recherche dans une base de données.

Historique

Dans les années 1970 et 80, les premiers ordinateurs quantiques naissent par retournement dans l’esprit de physiciens tels que Richard Feynman, Paul Benioff, David Deutsch ou Charles H. 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 dépasser 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 utilisant un circuit (théorique) de calcul quantique qui permet 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 puis bat ce record l’année suivante avec un calculateur 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. Ces calculateurs à 7 qubits 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 ;
en 2006, Seth Lloyd, professeur au Massachusetts Institute of Technology (MIT), 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 (p. 24) l’existence de calculateurs quantiques à 12 qubits¹⁰ ;
en avril 2006 l’Institut de traitement de l’information quantique de l’université d’Ulm (de) en Allemagne présente la première micropuce européenne linéaire tridimensionnelle qui piège plusieurs atomes ionisés Ca+ de manière isolée ;
le 14 décembre 2007, l’université du Queensland annonce travailler sur des circuits quantiques optiques¹¹ ;
en 2009, des chercheurs de l’université Yale créent le premier processeur quantique rudimentaire transistorisé de 2 qubits, capable d’exécuter des algorithmes élémentaires¹² ;
en 2010, une équipe de l’université de Bristol crée un processeur quantique optique, en silicium, capable d’exécuter l’algorithme de Shor¹³ ;
le 3 mars 2011, des physiciens de l'Université de Sherbrooke trouvent un nouvel algorithme quantique important¹⁴. En 2011, le dispositif le plus complexe a été mis au point à l'université d'Innsbruck et comporte 14 qubits¹⁵ ;
en 2012, Enrique Martín-López, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou et Jeremy L. O'Brien de l’université de Bristol créent un dispositif quantique optique, capable de factoriser le nombre 21 en exécutant l’algorithme de Shor¹⁶.

La controverse D-Wave

La société D-Wave a annoncé officiellement le 13 février 2007¹⁷ avoir réalisé un ordinateur quantique à base solide de 16 qubits¹⁸. Ce calculateur serait cependant limité à certaines opérations quantiques d'optimisation, comme celui du « voyageur de commerce¹⁹ ». Aucun prototype n’a été dûment testé par des spécialistes reconnus des ordinateurs quantiques, pour des raisons alléguées de secret industriel (le prototype n’était pas présent durant la conférence). Ces machines utiliseraient une puce nommée Europa qui fonctionne uniquement en milieu cryogénique. Reflétant le sentiment d’une partie de la communauté scientifique, Scientific American reste réservé²⁰. Les problèmes combinatoires résolus (sudoku) le sont moins vite qu’avec un simple ordinateur. Il n’y a là rien de surprenant au vu des caractéristiques de l’appareil, mais de ce fait on ne peut exclure totalement une opération du type Turc mécanique ayant simplement pour objectif de lever des fonds, d’autant que D-Wave promettait un ordinateur quantique à 32 qubits pour la fin de l’année 2007, et un ordinateur à 512 puis à 1024 qubits d’ici l’année suivante²¹.

Des débuts difficiles

En décembre 2007 et d’après le site même du constructeur, les seules nouvelles concernant D-wave depuis février auront été sa participation à une conférence sur le calcul massif²² et la démonstration alléguée d’une machine à 28 qubits²³ en novembre, commentée en détail par Tom's Hardware²⁴ en juillet 2008. La compagnie affirme alors maintenir ses objectifs de 512 qubits au second trimestre 2008 et 1024 qubits fin 2008, et assuré que la commercialisation des calculateurs quantiques était bien « une question d'années et non de décennies » ; elle a mentionné aussi son intention de rendre son calculateur et les capacités de corrélation très rapides de celui-ci accessibles à des chercheurs via l’Internet (Tom’s Hardware). Début décembre 2008, le site de la compagnie n’avait plus donné d’autres nouvelles depuis la fin de sa levée de fonds.
Le 14 avril 2009, elle annonce en fin de compte une puce de 128 qubits²⁵.

Première percée dans le monde industriel

En décembre 2009, un accord annoncé entre cette société et Google la remet sous les feux de l'actualité²⁶. En octobre 2010, elle présente dans le cadre des Google Techtalks le principe d'un classifieur quantique à grande échelle effectuant son apprentissage par une méthode de recuit²⁷.
En mai 2011, D-Wave vend à la société américaine de l’armement Lockheed Martin, pour 10 millions de dollars, un calculateur annoncé de 128 qubits, sur la nature quantique duquel planent cependant des doutes²⁸.

Acceptation d'une communication par l'ACM

Le 7 mai 2013, Amherst College annonce avoir effectué les premiers tests combinatoires où une machine de D-Wave batte largement un ordinateur classique²⁹. Néanmoins, on peut être surpris que cette étude ait été confiée à cet établissement et non à l'un de ceux beaucoup plus renommés en informatique que sont le MIT, Dartmouth, Harvard, Cornell, Stanford, Caltech ou Berkeley.
Une communication³⁰ est cependant acceptée sur le sujet par la très sélective ACM après revue par un comité d'experts, pour présentation le 15 mai 2013 à sa conférence annuelle sur l'informatique extrême³¹. IEEE Spectrum³²^,³³, référence en ingénierie, au départ très critique³⁴, puis sceptique³⁵, puis interrogative³⁶ prend acte du fait et fournit des précisions sur les résultats pratiques du calculateur selon le type de problème, allant de la moyenne d'une station de travail du moment à 3600 fois la performance de celle-ci³⁷. Le rapport peut sembler faible comparé à celui d'un supercalculateur massivement parallèle, mais les problèmes traités ont été choisis parce que ne faisant pas appel au parallélisable (comme les grands calculs matriciels), mais au contraire à la combinatoire.
Technology Review, revue du MIT, donne quelques précisions³⁸ : le circuit de calcul quantique fonctionne à 0.02 Kelvin (le calculateur réclame une température cryogénique pour éviter toute décohérence en cours de calcul), et a été mis en compétition avec une simple station Lenovo 2.4GHz quad core Intel munie de 16 Gio de RAM. La machine est donnée comme comportant 439 qubits, ce qui est énorme : (s'il s'agissait d'un calculateur quantique général, ce qui n'est pas établi, il dépasserait largement les 300 qubits. Or un calculateur quantique général de 300 qubits permettrait selon David Deutsch de simuler - théoriquement - la formation de tout l'univers depuis le Big Bang³⁹). Le nombre de qubits utilisés pour la détection/correction d'erreur, s'il y en a, n'est cependant pas précisé. De même, D-Wave ne précise pas si son calculateur est général ou bien comporte des contraintes d'utilisation.
La situation ressemble curieusement à celles des ordinateurs en 1953 : machines onéreuses, demandant des conditions physiques délicates, de prix élevé, coûteux à programmer encore faute de spécialistes, de recul et de théorie, et dont personne ne sait encore vraiment évaluer le potentiel. On peut se rappeler Thomas J. Watson expliquant qu'il voyait un marché dans le monde pour à peu près cinq ordinateurs.
La revue Scientific American a consacré le 19 juin 2013 un article à D-Wave et à la controverse existante autour de son produit⁴⁰.

Les « qubits solides » de Saclay et de Yale

En 2001, le CEA a mis au point une puce en silicium utilisant trois nanojonctions Josephson appelée le quantronium : deux jonctions servent de qubit, la troisième sert d'instrument de mesure. Pour les qubits, ces circuits électroniques contiennent des états de spin dans des boites quantiques semi-conductrices. À long terme, ces systèmes "solides" offrent des perspectives intéressantes d'intégration à grande échelle⁴¹.

Le 28 juin 2009, la revue Nature rend compte de la réalisation par une équipe de l’université Yale d’un circuit de calcul quantique solide pouvant être utilisé à terme dans un calculateur quantique⁴². Chacun des deux atomes artificiels (ou qubit) sont construits de plus d’un milliard d’atomes d’aluminium mais agissent comme un seul qui pourrait occuper deux différents états d’énergie⁴³.

Réalisations physiques

Un ordinateur quantique pourrait être implémenté à partir de toute particule pouvant avoir deux états à la fois excité et non excité 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.

Contraintes physiques

On pourrait imaginer utiliser une molécule microscopique, pouvant contenir plusieurs millions de protons et de neutrons, comme ordinateur quantique. Celui-ci contenant 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 (on parle alors de calcul adiabatique), toute observation ou tout effacement de données 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 d’un 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 conservant des informations supplémentaires non directement utiles. Toutes les portes classiques ont un équivalent quantique.

Il existe des systèmes quantiques isolés naturellement comme les noyaux de certains atomes. Certains, comme le carbone 13, possèdent un moment cinétique, un spin, et peuvent donner lieu à différents états quantiques. Les cristaux de diamant qui contiennent des isotopes du carbone 12 (les noyaux du diamant sont composés jusqu’à 1 % de noyaux de carbone 13) permettraient théoriquement à température ambiante de stocker et de manipuler de l’information quantique. Une première technique consiste à manipuler par laser le spin des électrons d’un atome d’azote constituant les impuretés du diamant, et ainsi agir sur le couplage entre le spin de ces électrons et celui des noyaux du carbone 13⁴⁵.

Projets en cours

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 œuvre de la physique théorique pointue. Les projets suivants semblent avancer à un rythme intéressant :

les circuits supraconducteurs avec jonction Josephson. Cette technique est très malléable : il s’agit de dessiner des circuits suffisamment résistants à 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 davantage à l’aide d’un résonateur et d’un SQUID ;
les ions piégés ; cette technique a donné le système possédant le plus de qubits intriqués.^{[réf. nécessaire]} ;
la résonance magnétique nucléaire ;
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ésonantes ;
les boîtes quantiques (« quantum dots » en anglais) : ce sont des systèmes macroscopiques qui possèdent, malgré tout, les caractéristiques quantiques nécessaires pour l’élaboration d’un ordinateur quantique. On appelle parfois de tels systèmes des atomes artificiels. Cette technique utilise des matériaux courants dans l’industrie des semi-conducteurs : silicium ou arséniure de gallium. Elle se subdivise en deux branches : l’une exploitant la charge électrique des qubits, l’autre leur spin (voir l’article spintronique).
beaucoup d’autres projets plus ou moins avancés.

Plusieurs projets semblent susceptibles d'exploitation industrielle, mais les problèmes de base demeurent. 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. 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.

Prix Nobel 2012

Le Prix Nobel 2012 de physique est allé conjointement à Serge Haroche et David Wineland pour leurs travaux conjoints sur le maintien et l'observation des qubits⁴⁶.

Principe de fonctionnement des calculateurs quantiques

Le fonctionnement des calculateurs quantiques peut paraître mystérieux au premier abord : la théorie quantique est une théorie décrivant des probabilités de présence. Comment dès lors concilier ce concept d’aléa avec un calcul qui se veut déterministe ?

Idées de la mécanique quantique

En fait, les fonctions d’onde, sont issues de calculs tout ce qu’il y a de plus déterministes. La source d’aléa est dans l’acte d’observation lui-même, c’est-à-dire la mesure. En effet, suite à une mesure, le système quantique et son observateur se fixent dans un état avec une certaine probabilité. On peut éliminer cette incertitude en formulant des expressions ne se traduisant que par oui ou par non (par exemple : « cette combinaison est compatible avec la clé » / « cette combinaison ne peut pas être la clé ». Pour certains algorithmes, il est nécessaire d’effectuer les calculs plusieurs fois jusqu’à ce que la réponse vérifie une certaine propriété.
En mécanique quantique, une concentration diffuse d'énergie (que l'on n'a le droit de nommer particule qu'après observation, car elle ne possède encore ni localisation ni vitesse définie) possède de multiples états simultanément, ce qui se nomme superposition. Une métaphore est celle du chat de Schrödinger qui est, avant observation, à la fois mort et/ou vivant.
Voir article spécialisé Chat de Schrödinger.
De même, lorsqu'un chat dort, il est immobile, et l’on ne peut pas dire juste en le regardant s’il dort ou s’il est mort. Le chat n'est donc pas tel quel observable sans interaction.

Si on essaie de réveiller le chat et que celui-ci ne se réveille pas, on a bien observé qu'il est mort. s'il se réveille, il ne l'est évidemment pas.
Paradoxe : en réveillant le chat, l’observateur altère cet état qu’il voulait observer et ne peut donc plus l’observer. On peut imaginer le chat endormi (probabilité = 50 % = une chance sur deux), puis le vérifier ensuite en essayant de le réveiller. On ne transmet à l'extérieur les résultats de l’observation que si le chat se réveille.
Avec seulement deux états possibles, le raisonnement est simple. Il se complique si l’on imagine plusieurs chats à étudier en même temps et/ou trois états possibles (mort, endormi, ou superposition (ce qui est possible pour une particule isolée).^{[pas clair]}

Au niveau quantique, il ne s’agit pas juste d’un modèle rendant compte de notre ignorance du système. Les distributions d'énergie (puisqu'avant observation, nous n'avons nul droit de parler de particule) possèdent bien cet état superposé et il en découle quelques propriétés inhabituelles à notre échelle. Une mesure sur un système quantique va fixer le couple formé par l'observateur et lui, avec des probabilités données, dans un des états possibles, qui sera alors constatable par tous les autres observateurs sans aléa aucun. L'interprétation d'Everett propose une signification possible de ce phénomène.

Le qubit

Article détaillé : Qubit.

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 ordinateur 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). L’ordinateur quantique calcule en manipulant ces distributions. On n’a donc pas trois états en tout mais une infinité.
De plus, l’état de plusieurs qubits réunis n’est pas seulement une combinaison des états respectifs des qubits. En effet, si un qubit est dans une quelconque superposition d’états $\alpha \cdot \left| 0 \right\rangle + \beta \cdot \left| 1 \right\rangle$ , deux qubits réunis sont quant à eux dans une superposition d’états $\alpha \cdot \left| 00 \right\rangle + \beta \cdot \left| 01 \right\rangle + \gamma \cdot \left| 10 \right\rangle + \delta \cdot \left| 11 \right\rangle$ , avec $|\alpha|^2 + |\beta|^2 + |\gamma|^2 + |\delta|^2=1$ . Il s’agit cette fois d’employer la superposition des quatre états pour le calcul. C’est pourquoi la puissance de calcul théorique d’un ordinateur quantique double à chaque fois qu’on lui adjoint un qubit. Avec dix qubits, on a 1024 états superposables, et avec n qubits, $2^n$ .
Un ordinateur classique ayant trois bits de mémoire peut stocker uniquement trois chiffres binaires. À un moment donné, il pourrait contenir les bits « 101 » ou une autre combinaison des huit possibles (2³). Un ordinateur quantique ayant trois qubits peut en fait stocker seize valeurs, assemblées deux par deux pour former huit nombres complexes (il est donc dans une superposition de ces huit états). 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$

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 300, il y aurait eu plus de lignes que d’atomes dans l’univers observable.
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 huit états à la fois. La deuxième colonne montre l’amplitude pour chacun des huit états. Ces huit 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 de trois bits classiques et efface les huit 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^2+b^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êmes probabilités. La liste des nombres complexes peut être imaginée comme un vecteur à huit éléments. À chaque étape de l’algorithme, le vecteur est modifié par son produit avec une matrice qui correspond à une opération quantique.

Technologies

Un article publié en avril 2008 par Scientific American fait état d’une avancée⁴⁷ vers le calculateur quantique utilisant l’effet Hall quantique fractionnaire.

Simulation d’un calculateur quantique

Perl

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 utilisable pour écrire et tester, en version maquette à quelques qubits simulés, des programmes écrits pour la logique quantique. 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 toucher en rien au programme Perl lui-même excepté en ce qui concerne le nombre de qubits spécifié. On pourra alors tirer parti des capacités d’un calculateur quantique et effectuer ainsi des calculs plus complexes à temps égal.
Le module munit Perl de deux fonctions testant globalement les tableaux : any() et all(). Dans la simulation, ces fonctions travaillent par itération sur les éléments et donc en un temps O(N). Dans un calcul quantique, leur temps d’exécution serait indépendant de N.
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. Une extension de ce dernier nommé QHaskell (quantum Haskell) existe depuis 2006⁴⁹
Le MIT, pour sa part, a placé en Open source un outil d’aide à l’architecture de circuits quantiques (théoriques) simples⁵⁰.

C

Les dépôts Debian et Ubuntu (Linux) proposent également via le gestionnaire de paquets APT la bibliothèque de sous-programmes C libquantum⁵¹, qui implémente la simulation d'un registre quantique. Une interface permet de lui appliquer des opérations simples comme la porte de Hadamard. Les mesures se font soit (comme sur un véritable calculateur quantique) qubit par qubit, soit pour plus de simplicité sur le registre entier.
Les implémentations des algorithmes de Shor et de Grover sont fournies à titre d'exemple, ainsi qu'une interface pour la correction d'erreur quantique (QEC) et le support de la décohérence. Les auteurs en sont Bjorn Butscher & Hendrik Weimer.

Budgets

Selon un rapport de l'Union européenne⁵², les États-Unis consacrent 75 millions d'euros à ces recherches contre 8 millions pour l'Europe. Le Canada dépenserait 12 millions d'euros par an, le Japon 25 millions et l'Australie 6 millions⁵³.

Avenir commercial ?

Même si les problèmes techniques posés par la réalisation de calculateurs quantiques étaient résolus à terme, leur avenir commercial immédiat ne se situe pas nécessairement dans le grand public, tout dépendant é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.
Il est à noter qu'un appareil électronique classique dédié exclusivement au calcul fortement combinatoire a existé dans les années 1970 où il servait à optimiser les roulements de la SNCF sous contraintes. Il s'agissait de l'"Optimateur" Cybco C100-1024, qui opérait par exploration câblée de toutes les solutions possibles en allégeant ses calculs par des considérations d'impossibilité et de symétrie⁵⁴. Le besoin existe donc depuis déjà plusieurs décennies et sa résolution par des circuits spécialisés a même fait l'objet de brevets⁵⁵.
En novembre 2008, Aram W. Harrow, Avinatan Hassidim et Seth Lloyd ont publié⁵⁶ une méthode quantique permettant de résoudre des systèmes d’équations linéaires à matrices creuses en un temps O(log(n)) au lieu de O(n).
En réseaux de neurones, la méthode dite du greedy learning⁵⁷ consomme également beaucoup de combinatoire et est donc signalée par D-Wave en 2009 comme une application possible⁵⁸.
Quelques autres pistes envisageables :

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⁵⁹.

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. Le calcul quantique apporte un avantage quantitatif énorme en matière combinatoire, mais aucun en entrées-sorties, les sortie restant en particulier séquentielles (on ne peut les obtenir que bit par bit, toute observation de l'état quantique⁶⁰ cassant tout le reste de l'état interne, et demandant que soit refait le calcul pour l'observation d'autre chose) : ils semblent donc adaptés essentiellement aux types de problèmes dans lesquels les calculs combinatoires sont importants par rapport aux sorties⁶¹ (ce qui est exactement le cas du cassage de clé). Cette taille modeste, en regard du moins du traitement, des entrées et des sorties se prêterait à l'usage à distance par Internet. En un tel cas, les prérequis d'encombrement et éventuellement de cryogénie ne seront plus aussi aigus.
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)⁶². Des émulateurs de modèles quantiques ont été construits pour enrichir le débat (cf. section sur l’exemple en Perl.).
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.

View

Translate

vendredi 16 août 2013

Calculateur quantique

Sommaire