Griffonnages

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.