Parce qu'il est facile de critiquer et de se moquer, je vous propose, en réponse, un
tour d'horizon des principales erreurs liées à l'informatique quantique. Et
puis, par soucis d'honnêteté intellectuelle, je fais avant tout remarquer à mes
lecteurs, que vue la hauteur où les autres blogueurs ont placé la barre, je ne
risque pas grand'chose. Et l'autre argument qui a fini de me décider d'écrire
ce billet est la lecture de la page wikipedia Ordinateur quantique, qui ne
mériterait que d'être effacée.
1. L'ordinateur quantique n'est pas un ordinateur
Un ordinateur est une machine qui prend deux entrées : un programme et
des données puis exécute ce programme avec les données fournies. Bref un
ordinateur peut faire tourner n'importe quel programme (décidable).
Actuellement, on parle plutôt de calculateur quantique car ce que les
physiciens essayent de faire ne pourra calculer qu'une seule fonction. Ou, si
vous préférez, il y a aura un calculateur pour le traitement de texte, un
calculateur pour naviguer sur internet,etc... pas très commode.
Mais est-ce qu'un ordinateur quantique peut exister ? La
réponse est oui, en terme savant, on dit qu'il existe une machine de Türing
quantique universelle.[1] Quelle en sera son architecture ?
Je n'en sais rien, et je ne sais même pas si des gens le savent, mais il est
prouvé qu'un tel système peut exister.
2. Un calculateur quantique ne fait pas tous les calculs en
parallèle
L'erreur principale qu'on entend à propos de l'ordinateur quantique, c'est
qu'il fait tous les calculs en parallèle, très pratique donc pour résoudre un
sudoku puisqu'il essaye toutes les grilles en même temps. Et bien c'est
faux.
Cette erreur est due à la mauvaise compréhension d'un phénomène purement
quantique : la superposition, ou plus vulgairement appelé chat de
Schrödinger.
Lecteurs, permettez-moi une digression sur le chat de Schrödinger, et
laissez-moi vous expliquer que je trouve cette image nulle et incompréhensible,
et qu'elle se trouve, par son côté un peu sexy, le chat est vivant et mort à
la fois
, finalement contre-productive.
Vous connaissez tous les probabilités. Avec des probabilités, on dit que le
chat est 50% mort + 50% vivant. Et là en fait, il n'y a pas grand'chose de
quantique, juste un ersatz. Ce que l'on manipule en mécanique quantique, ce ne
sont plus les probabilités, mais les amplitudes de probabilité. Et ça fait
toute la différence. Une amplitude de probabilité, c'est un nombre positif ou
négatif[2] dont son carré est une probabilité. Ainsi en
mécanique quantique on écrira pour le chat :
- 1/√(2) mort + 1/√(2) vivant
- 1/√(2) mort - 1/√(2) vivant
- - 1/√(2) mort + 1/√(2) vivant
- - 1/√(2) mort - 1/√(2) vivant
Et lorsqu'on ouvrira la boîte pour savoir s'il est mort ou vivant, nous
aurons une probabilité de 50% de le trouver dans un état ou un autre. Mais
qu'est-ce que ça change alors ? Tout, parce que cela permet de faire des
interférences, et que, précisément, ce sont ces fameuses interférences qui
permettent de faire certains calculs plus rapidement.
Un calcul, c'est une série d'étapes qui renvoient des résultats
intermédiaires, la dernière renvoyant le résultat final. Dans un calcul
classique, on sait exactement quelle étape on va effectuer ensuite, pas dans le
calcul quantique, on choisi l'ordre des étapes avec des amplitudes de
probabilité en fonction du résultat de l'étape courante.
Comment fait-on alors pour savoir la probabilité de lire le bon
résultat ? On fait la somme des amplitudes de probabilité de tous les
chemins qui, d'étapes en étapes, arrivent sur la bonne réponse. Puis ensuite on
élève cette quantité au carré. Et pareil pour les mauvaises. Si un chemin a une
amplitude de probabilité positive et un autre chemin une amplitude de
probabilité négative, alors il va y avoir une interférence destructive, et
cette réponse n'apparaîtra pas.
Faire un algorithme quantique, c'est se débrouiller pour qu'il y ait des
interférences constructives sur les chemins qui mènent à la bonne réponse, afin
qu'on puisse lire la réponse attendue avec une grande probabilité, et faire des
interférences destructives sur les chemins qui mènent aux mauvaises
réponses.
Ainsi, pour faire court, on part de toutes les entrées possibles, et le
calcul se faisant, la probabilité de la bonne réponse augmente, ce qui n'a,
avouez-le, pas grand'chose à voir avec faire tous les calculs en même temps, et
puis, hop, par magie, choisir à la fin le bon résultat.
3. Un calculateur quantique ne sait pas résoudre un problème NP-complet
(enfin, on pense)
Commençons par une page culturelle :
De tout temps, les informaticiens se sont entêtés à classer les
problèmes.[3] Il existe plusieurs centaines de classes de
problèmes, mais les deux plus connues sont P et
NP. P est la classe des problèmes qu'il est
possible de résoudre en temps Polynomial avec un ordinateur classique, c'est à
dire, qu'on sait les résoudre vite. NP est la classe des
problèmes qu'il est possible de résoudre en temps Polynomial avec un ordinateur
Non-déterministe.[4]. NP c'est la classe des
problèmes très longs à résoudre, mais si on possède une solution, c'est facile
de vérifier qu'il s'agit de la bonne.
Un problème dans P est donc aussi dans
NP.
LA question de l'informatique théorique depuis des années, c'est de
savoir si P=NP ou
P≠NP. La quasi-unanimité va à l'hypothèse
P≠NP à notre époque, il n'en allait pas de
même il y a 30 ans.
Dans NP, la classe des problèmes difficiles, il y a ceux
qui sont vraiment difficiles, c'est à dire qu'en résoudre un permet de résoudre
ensuite très vite tous les autres problèmes dans NP, c'est
problèmes sont dit NP-complets.
Tous les problèmes dans NP connus, ont été démontrés être
soit dans P, soit être NP-complets. Tous,
sauf 2. Peut-être sont-ils dans P, peut-être sont-ils
NP-complets, peut être entre ces deux classes, on ne sait pas.
Il s'agit du problème dit de l'isomorphisme de graphe et de celui de la
décomposition d'un entier en facteurs premiers.
Fin de la page culturelle, revenons au quantique.
Aucun problème NP-complet n'a été résolu en temps
polynomial avec un ordinateur quantique. Peut-être un jour, mais la communauté
scientifique qui s'intéresse à cette question est très perplexe et n'y croit
plus.
4. Il y n'y a pas que 2 algorithmes quantiques
Le calcul quantique permet de calculer exactement les mêmes fonctions qu'un
ordinateur classique. Donc tous les algorithmes classiques peuvent exister en
quantique. Ce qui se passe, c'est qu'il y a certains problèmes que l'on sait
résoudre plus rapidement grâce au calcul quantique, et il y en a aussi pour
lesquels le calcul quantique n'améliore pas même d'un ι la rapidité.
Alors quels sont ces deux algorithmes tellement connus qu'ils occultent les
autres ?
- L'algorithme de Shor (1994) qui permet de calculer efficacement (P) le
logarithme discret. Un truc de mathématiques pures apparemment, sauf que savoir
calculer le logarithme discret efficacement permet la décomposition d'un entier
en facteurs premier, et ça, c'est casser la plus grande branche de la
cryptographie moderne, celle qui est utilisée aussi bien dans le
https que dans les cartes bleues.
- L'algorithme de Grover (1995) qui permet de rechercher un élément dans une
base de donnée non triée en O(√n), c'est impressionnant, un élément est trouvé
1000 fois plus rapidement avec un calculateur quantique pour une base de
données d'un million d'entrée, ça pourrait presque faire envie à
Google.[5]
Il y a aussi des algorithmes qui permettent de calculer des polynômes plus
rapidement, mais c'est anecdotique.
En revanche, un algorithme dont on devrait beaucoup entendre parler la suite
est celui de Farhi, Goldston et Gutmann, découvert en février 2007 pour résoudre en
√n le problème du NAND-Tree. J'ose pas trop en parler de peur de dire n'importe
quoi tellement je connais peu. Je préfère vous indiquer l'article sur le blog de
Scott Aaronson qui en parle, mais c'est en anglais.
5. La cryptographie quantique n'est pas une conséquence de l'ordinateur
quantique
Je sais, il est tentant de répondre à : Alors, comment va-t-on faire
pour sécuriser nos échanges si RSA est cassé ?
par Heureusement, grâce à
la mécanique quantique, encore elle, il existe une parade
La cryptographie quantique est apparue en 1984 dans le célèbre article
[BB84], alors que l'algorithme de Shor date seulement de 1994, soit dix ans
entre les deux.
Dans un élan de générosité, je répondrai, dans la mesure des mes moyens,
évidement, à toutes les questions qui, malgré les trésors d'ingéniosité que je
viens de déployer, continuent de se bousculer dans votre tête.
