Griffonnages - Tag - Ordinateur quantique

Un peu de wikipedia bashing

Celui — Mon, 16 Jun 2008 00:43:00 +0200

Je m'étouffe quand je lis ce genre de connerie^[1] dans wikipedia :

Des circuits de calcul quantique apportent donc un plus aux ordinateurs classiques dans quatre types d'applications :
— la décomposition en produit de facteurs premiers ;
— le logarithme discret ;
— les simulations de physique quantique.
— La recherche d'un élément dans une grande liste (Algorithme de Grover)

Voici ma liste :

Simulations de mécanique quantique
Problèmes d'algèbre
1. Décomposition en facteurs premiers et logarithme discret (Algorithme de Shor)
2. Décomposition de groupes abéliens
3. Recherche spatiale
4. Résolution des équations de Pell
5. Recherches d'idéaux
6. Approximations de sommes de Gauss
7. Décalage de symboles de Legendre
8. Problème du sous-groupe caché
Problèmes de recherche
1. Sans structure (Algorithme de Grover)
2. Collision
3. Moyenne
4. Graphes connexes
5. Arbres couvrant minimal
6. Chemin le plus court avec une source unique
7. Flot en réseau
Approximation de problèmes #P-complets
1. Polynômes de Jones
2. Polynômes HOMFLYPT
Marches quantiques
1. NAND Tree (Algorithme de Farhi)
  1. Évaluation de formules booléennes
2. Recherche de triangles
3. Recherche d'éléments distincts
4. Vérification de multiplication de matrices
5. Test de la commutativité d'un groupe

Et encore, je ne suis pas à jour.

Notes

[1] Cet article est un exemple du pire de wikipedia, il y a des erreurs ÉNORMES, il faudrait le réécrire en entier.

L'ordinateur quantique peut-il tout résoudre ?

Celui — Sat, 17 May 2008 19:35:00 +0200

« L'ordinateur quantique peut-il tout résoudre ? » telle est la question en une du numéro de mai de « Pour la science »

Comme je n'ai pas trop le temps de bloguer, et que le web 2.0, c'est le « user generated content » discussions et questions libres en commentaires. Qu'en avez-vous pensé ? Quelles questions vous restent-ils ? L'ordinateur quantique, qu'en pensez-vous, que voulez-vous savoir sur lui ?

Un billets de commentaires, j'espère.

Mon sujet, c'est ici

Celui — Fri, 14 Dec 2007 13:00:00 +0100

Comme funnyface, je trouve qu'énoncer le sujet de ma thèse en société, ça ne se fait pas. Ça relève de la vulgarité et de la prétention. (et en plus, il n'y a pas Foucault dedans). Mais les gens sont curieux, ils insistent Allez, Celui, dis-moi le sujet de ta thèse, alors je suis obligé d'assurer mes arrières Es-tu bien sûr que tu veux le savoir ?. Là j'espère voir poindre une lueur de doute, mais ma question a toujours l'effet inverse : Bien sûr que je veux savoir !

Erreur fatale, blue screen of the death, Et c'est sur moi que ça retombe, les gens attendent des explications, de la vulgarisation, comme si je n'avais pas dit assez de gros mots comme ça.

Dorénavant, j'ai la solution, je répondrai va voir sur mon blog, y a la réponse C'est le niveau 1 de la pédagogie, mais ma vie sociale est à ce prix-là.

Je fais de la cryptographie, c'est-à-dire coder des messages, les envoyer, les décoder. Le truc important, c'est qu'un espion, s'il a le message codé ne puisse pas le décoder. C'est pour ça que vous pouvez commander mes cadeaux de noël sur Internet sans (trop de) risque.

Mais voilà, il y a une saloperie, il y a un théorème d'impossibilité. C'est un théorème qui commence par Il est impossible de ; et dans mon cas c'est Il est impossible de faire un protocole de cryptographie inconditionnellement sûr. Au jeu du chat et de la souris, il est impossible à la souris de trouver un endroit sûr. Ça m'emmerde pour mes cadeaux.

Donc ce qu'on cherche, c'est un protocole où pour l'espion (que l'on appelle Ève entre nous) il soit très difficile de décoder le message. C'est à dire que le problème décoder le message soit compliqué. Ça un vrai truc d'informaticien, on a des milliers de problèmes qu'on passe notre temps à trier, à ranger, à classer. Et des classes de problèmes, nous en avons à revendre. Il y a en tellement, un bestiaire impressionnant, qu'il existe même un zoo. Il y en a pour tous les goûts : des classes de problèmes extrêmement simples aux plus ardus.

Les deux classes les plus connues répondent incontestablement aux doux noms de P et de NP. Dans P il y a les problèmes pas trop durs, dans NP des problèmes (que l'on croit) difficiles. La question la plus fondamentale aujourd'hui en informatique, c'est de démontrer que P≠NP.

Une immense partie de la cryptographie actuelle est basée sur un algorithme qui s'appelle RSA (trouvé par Rivest, Shamir et Adleman). Le problème qu'Ève doit résoudre pour espionner la conversation est dans NP. C'est sacrément compliqué pour elle de le faire, même si ce n'est pas impossible.

Un exemple ? Si je vous dit que 159623548 x 5597469526 = 893487945561998248, vous prenez votre calculatrice pour vérifier, c'est facile, la multiplication est dans P. Maintenant, je vous demande de trouver deux nombres à 10 chiffres tels qu'en les multipliant vous obtenez 893487945561998248, c'est une autre histoire, c'est compliqué, c'est dans NP. C'est sur principe que reposent les algorithmes modernes. (À la différence près qu'au lieu d'utiliser des nombres de 10 chiffres, on utilise des nombres de plusieurs centaines de chiffres)

Mais voilà, en 1994, Peter Shor a montré que si Ève avait un ordinateur quantique, alors elle peut facilement écouter les conversations. Un chat avec un ordinateur quantique, c'est un chat qui coure plus vite. Il ne fait rien de magique, rien de plus que ce qu'il pouvait faire avant, il le fait juste plus vite. Donc ce que j'essaye de faire, c'est de trouver un protocole, mieux qu'RSA (en tout cas sur le papier) où Ève, même avec un ordinateur quantique, ne puisse pas écouter la conversation.

Dit comme ça, on dirait que je ne sais pas trop où je vais. C'est faux. Il y a rarement quelque chose de fondamentalement nouveau en recherche. Je joue au Légo, j'assemble des briques qui existent déjà, mais à la Celui, j'utilise de vieux outils, même si personne ne les utilise de cette manière. C'est ce qui continue de m'émerveiller, chaque fois que j'ajoute un élément, çà me donne une idée de comment continuer. De temps en temps, il faut casser un bout pour le reconstruire différemment, mais la maison immanquablement prend forme.

Quand on y réfléchis bien, je ne suis qu'un gamin qui continue de jouer au Légo, pour que vous puissiez continuer vos activités d'adultes qui nécessitent le secret. À chacun sa place, et j'aime la mienne.

Ça fait une bonne introduction pour ma thèse, non ?

Ce que l'ordinateur quantique n'est pas

Celui — Sun, 02 Sep 2007 20:00:00 +0200

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.

Notes

[1] Un ordinateur étant une machine de Türing universelle

[2] complexe dans le cas général

[3] Oui, de tout temps, déjà dans les années 30, c'est pour dire...

[4] NP ne veut donc pas dire Non Polynomial !

[5] Parce que leur base de données sont totalement structurées, et que donc, cet algorithme n'est pas vraiment exploitable...