Bonjour tout le monde.

Je crée ce topic comme lieu de spéculation en tout genre sur l'ordinateur quantique ainsi que pour connaitre les dernières nouvelles en matières de développements de l'ordinateur du futur.

Jusqu'à présent les ordinateurs ont toujours fonctionné à parti de signaux éléctriques alternatifs matérilisant les  bits de données : présence de courant = 1, abscence = 0. Pour effectuer tous les différents calculs nécéssaire au bon fonctionnement d'un ordinateur, nous utilisons des microprocesseurs fonctionnant sur ce principe. En effet, les CPU actuels sont de véritables circuits imprimés colossaux comprenant des millions de transistors, un composant électronique fournissant ou non un courant électrique matérialisant ainsi les bits de données. Le CPU le plus puissant à l'heure actuel pour les consommateurs "grand public", l'i7 980x possède plus d'un milliard de transistor avec un die gravés en 32 nm. Si l'on veut continuer d'augmenter la performance des microprocesseurs en maintenant le même principe de fonctionnement, il faut alors augmenter encore et encore le nombre de transistors et donc il faut diminuer la finesse de gravure. Intel prévoit la vente de processeur gravés en 22 nm pour 2012 pour continuer à réduire cette finesse vers les 5 nm à l'horizon 2020.

Pour donner un ordre d'idée, un atome mesure environ 1 angström soit : 0.1nm ; ce qui signifie que graver un die en 5nm implique que les transistors soient grands comme 50 atomes ! Cependant comment fais ton pour aller en dessous de 5 nm ? Là se pose une embûche physique insurmontable : les transistors deviennent tout simplement trop petits et étant constitués de quelques atomes, ils subiraient des interférences quantiques. Pour comprendre, il faut savoir que dans le monde de l'infiniment petit, les lois de la logique et de la mécanique classique ne s'appliquent pas. En effet, si l'on est capable de déterminer la position et la vitesse d'un objet parfaitement dans notre univers (exemple : les radars certains se reconnaitreront dont moi ) il est en revanche impossible de déterminer avec précision la vitesse et la position d'une particule du à son comportement ondulatoire. On se sert de fonction probabilistes pour déterminer déterminer sa position ou sa vitesse. Une particule peut aussi exister sous différents état de polarisation or quand on fait une mesure sur une particule, on détermine cette polarisation qui est fixé a priori par l'expérience. En fait, selon le principe d'incertitude d'Heisenberg, on ne peut observer l'infiniment petit parce que la présence de l'observateur influe sur le comportement de la matière. La meilleure illustration de ce phénomène reste l'expérience du chat de Schrödinger : mettons un chat dans une boite totalement hermétique et fermée contenant une fiole de poison. Tant que le chat reste dans la boite, il est impossible de déterminer si le chat est mort ou vivant : il existe dans les deux états mais lorsque qu'on ouvre la boite, le chat n'existe plus que dans un des deux états. Ceci tend à prouver que le comportement des particules selon la mécanique quantique reste difficile à prévoir et que le comportement électrique d'un transistor de quelques atome devient non conforme avec ce que l'on attend de lui.

Mais, les promesses de l'ordinateur quantique existent toujours et elles restent fondées. D'aucun diront que l'ordinateur quantique est comme le chat de schrodinger : à la fois mort et vivant. Mort parce que les difficultés techniques rencontées sont très nombreuses et vivant parce que les principes utilisés fonctionnent bel et bien et que les perfomances espérées en terme de calcul parallèle grâce au qubit (pour quantum bit) qui remplacerait le bit. Le qubit caractérise l'état quantique qui représente la plus petite unité de stockage d'information quantique contenue dans une particule (le plus simple étant un photon donc une particule de lumière au lieu d'électrons).

citation de wikipedia sur le sujet :
Le qubit se compose d'une superposition de deux états de base, par convention nommés |0> et |1> (prononcés : ket 0 et ket 1). Un état qubit est constitué d'une superposition quantique linéaire de ces deux états. Une mémoire à qubits diffère significativement d'une mémoire classique. Un bit classique se trouve toujours soit dans l'état 0, soit dans l'état 1. Un qubit se trouve, dans le cas général, dans une superposition de ces deux états, autrement dit une combinaison linéaire. On écrit que le qubit est dans l'état , les coefficients étant des nombres complexes vérifiant | α | 2 + | β | 2 = 1. En fait, on peut postuler arbitrairement que α est un nombre réel positif, car multiplier un état par un nombre complexe de module 1 donne le même état.
Lors de la mesure de la valeur du qubit, les seules réponses pouvant êtres obtenues sont 0 ou 1. La probabilité de mesurer l'état 0 vaut | α | 2, tandis que celle de mesurer l'état 1 vaut | β | 2. Après mesure, le qubit se trouve dans l'état mesuré (voir les articles concernant la physique quantique). On dit souvent que le qubit se trouve soit dans l'état 0, soit dans l'état 1, soit dans une superposition des deux. Cependant, il ne faut surtout pas comprendre que la superposition est un troisième état. Les états mesurables restent au nombre de deux, tandis que l'état du qubit n'est pas quelque chose de différent mais une somme des deux. De plus les états superposés sont en nombre infini, suivant les variations de α et β.

L'ordinateur quantique permettrait donc de faire d'énormes progrès dans les domaines de la simulation, de la sécurisation et de la cryptographie : un algorithme dû à Peter Shor permet d’utiliser un calculateur quantique pour « casser » le code RSA !! Cependant il ne fonctionne pas encore totalement, quoique : http://www.youtube.com/watch?v=Ava_BA4Colo

Des technologies utilisant les phenomènes quantique existent déjà : les ecrans LCD, le futur Lightpeak : la fibre optique pour carte mère mais le fonctionnement reste en bits. Vivement le qubit !

A part pour la cryptographie, la classe BQP ne contient pas énormément de problèmes concrets.  
La machine quantique ne fait presque pas gagner de temps sur les problèmes dans P et ne peut pas résoudre efficacement les problèmes NP.
 
En d'autres termes, pour jouer à Crysis et pour faire tourner Photoshop (problèmes parfaitement polynomiaux) on ne va rien y gagner (a fréquence et mémoire égale). Pour les problèmes d'optimisation (voyageur de commerce, SAT, 3-COL) on ne va pas y gagner beaucoup non plus.
 
Restent les problèmes BQP... Et ça ne fait pas beaucoup (factorisation, log discret, que des problèmes de crypto).
 
Bref, si on fait un calculateur quantique, a part foutre en l'air toute la cryptographie asymétrique (et donc rendre invalide tous le systèmes de signatures utilisés actuellement) on ne sera pas super avancé (a moins qu'on veuille faire des simulations quantiques, mais c'est du marché de niche).
 

 
Bon, ça reste super intéressant pour certains calculs scientifiques. Mais ne vous attendez pas à voir Firefox tourner plus vite sur ces machines.

tu as tout à fait raison mais je pense que quand même que la puissance de calcul qui pourrait etre offerte par les calculateurs quantiques peut intéresser la recherche scientifique, l'imagerie médicale etc.
 
de là à développer des machines quantiques pour le grand public, il y a effectivement un monde.
 
et puis je trouve intéressant de chercher un nouveau mode de fonctionnement

L'imagerie est un mauvais exemple : on n'y rencontre aucun problème qui soit dans BQP...

 
Il n'y à rien à y gagner non plus dans le domaine de l'intelligence artificiel ou des algorithmes de recherche (google & co)    
 
Perso je croyais que le processeur quantique était une sorte de super CUDA (comme sur les GPU Nvidia) mais au lieu de pouvoir faire 1000 calcul en parallèle, le nombre est théoriquement illimité ?
 
En tout cas merci pour ces précisions

koko90, est ce que tu peux nous préciser un peu ce que sont les problèmes PSPACE ? je comprends pas trop la significations de ces lettres P etc..
tu as bossé sur le sujet pour ton doctorat ?

J'ai bossé dessus en D.E.A. (enfin, ça serait un Master 2 aujourd'hui).
 
Pour résumer, on s'interesse à la complexité d'un problème en fonction de la taille de l'entrée et on classifie les problèmes avec ça.
 
On va commencer avec les problèmes sympa : ceux qui sont dans P. Donc qui sont en temps polynomial.
 
Par exemple on veut ajouter deux nombres de taille n (l'unité n'est pas importante, on va dire 2 entiers de n octets). L'addition se fait localement (il y a une retenue, à propager, et c'est tout). Donc il faut un temps linéaire et une mémoire linéaire par rapport à n (en gros, il faut n octets pour stoker le résultat, plus un octet pour la retenue).
On dira que la complexité et O(n). C'est un problème "facile". Si tu as des entrés 16 fois plus grosses, il suffit de 16 fois plus de temps et de 16 fois plus d'espace. C'est un problème polynomial dont la complexité est bornée par un polynôme de degrés 1.
 
Maintenant imaginons la multiplication. Si on la fait naïvement, avec l'algorithme enseigné au collège (celui qu'on utilise au papier et au crayon), il faut n² opérations pour multiplier des entiers de taille n. Donc la complexité est O(n²). Des entrées 16 fois plus grosses demanderont 16² fois plus de temps (donc 256 fois plus de temps). Niveau espace, ça reste linéaire si on ruse un peu. Mais on peut faire ça plus vite avec l'algorithme de Schönhage-Strassen (basé sur les transformées de fourrier). Ça donne do O(n*log(n)*log(log(n))). Des entrées 16 fois plus grosses demanderont 16*log(16)*log(log(n)=16*4*2=128 fois plus de temps. Dans les deux cas, on est toujours dans le cas d'une complexité polynomiale (bornée par le polynôme X²).
 
Dans la classe P on trouve en vrac : le tri, la recherche d'une entrée dans un tableau, la recherche d'un plus court chemin dans un graphe, la multiplication de matrices, etc. Presque tous les programmes qu'on utilise dans la vie de tous les jours (firefox, tes jeux, ton logiciel de rendu 3D, le truc qui reconstitue les images à partir des projection dans ta machine IRM, ton programme favori de compression vidéo) utilisent essentiellement des problèmes qui sont dans P. Pour ces problèmes, une machine quantique est inutile.
 
Ensuite il y a les problèmes NP. Ce sont les problèmes qui sont en TEMPS polynomial sur une machine non déterministe. Une machine non déterministe ça n'existe pas, c'est un phantasme de théoricien. Ça serait une machine qui devinerait la solution (par exemple en traitant tout les choix possibles simultanément) puis qui se contenterait de la vérifier. Donc pour qu'un problème soit en temps polynomial sur une machine non déterministe, il suffit d'avoir un algorithme qui teste la validité d'une solution en temps polynomial.
 
Un exemple de problème qui est dans NP est la 3-coloration d'une carte. L'entrée c'est lune carte combinatoire (n régions, k frontières). On veut calculer s'il existe une coloration des régions de la carte avec 3 couleurs seulement tel que deux régions adjacentes soient de couleur différente. Si on te donne une solution (a chaque sommet, on t'associe une couleur) alors tu peux la vérifier facilement. Donc le problème est dans NP. Par contre si on ne te donne pas la solution, tu doit essayer toutes les colorations possible, et il y en a 3^n... Là ça te prends un temps exponentiel sur machine déterministe (on dit que le problème est dans EXP). Une entrée 16 fois plus grosse prendra 43046721 fois plus de temps !
 
Bien entendu, il existe peut-être un algorithme intelligent qui résoudrait le problème de la 3-coloration d'une carte en temps polynomial. Si c'est le cas, alors P=NP. Tu gagnes un prix d'un million de dollars (le Millenium Prize), tu mets des centaines de chercheurs au chômage et tu peux faire écrouler l'économie planétaire en 10 minutes puisque tu as aussi cassé le logarithme discret et RSA.
 
On sait démontrer que si un problème est dans P, alors il est dans NP (donc la machine déterministe n'est pas plus "lente" pour les problèmes classiques). On sait aussi démontrer que si un problème est dans NP, on peut le résoudre sur une machine déterministe en prenant assez de temps (EXP, mais on peut rêver faire mieux). Donc une machine non déterministe ne résout pas plus de problèmes, elle les résout juste plus vite.
 
Ensuite il y a les classes en espace. LOGSPACE (aussi appelé L, mais j'aime pas) c'est les problèmes qui prennent un espace logarithmique par rapport à l'entrée. Je n'ai pas d'exemple intuitif sous la main. Ce qu'il faut voir, c'est que la limite en espace (logarithmique) entraine une limite en temps (par exemple, en log(n) bits, on a au plus 2^log(n) états, donc n états). Donc LOGSPACE est inclus dans P (et a fortiori dans NP).
 
Ensuite c'est PSPACE : espace polynomial mais pas de limitation en temps.
Si un problème prends un temps borné par un polynôme, alors il ne peut pas prendre un espace qui ne soit pas borné par un polynôme. Donc PSPACE contient P. Il est facile de démontrer qu'il contient aussi NP. Un problème dans PSPACE peut prendre un temps exponentiel (la limitation ici imposée ne concerne que l'espace).
 
Techniquement on a aussi les problèmes NPSPACE (espace polynomial sur une machine non déterministe). Mais on démontre qu'une machine non déterministe ne fait pas gagner d'espace sur de tels problèmes (donc NPSPACE=PSPACE).
 
La machine quantique n'est pas aussi puissante qu'une machine non déterministe, mais est un peu plus puissante qu'une machine déterministe. Elle peut résoudre efficacement certains problèmes d'une classe appelée BQP. Dans cette classe, on trouve essentiellement des problèmes de crypto.
 
PS : J'ai pas vraiment le temps de me relire...

ok merci pour l'explication, je ne connaissais pas cette classification. Ca me rappelle la prépa et les problèmes sur les espaces vectoriels hihi
 
Donc si je te suis bien : les problèmes P étant des problèmes linéaires assez simple à traiter, donc effectivement l'ordinateur quantique ferait gagner un pouillème de temps sur ces calculs ce que je conçois fort bien et donc un tel calculateur servirait surtout pour des problèmes NP.  
 
Comme tu l'as expliqué, on aurait alors un système qui serait très performant dans les problèmes non linéaires du style : résoudre des équations différentielles non linéaires comme on peut en trouver en météorologie par exemple. Je suppose que tu connais le principe mais els modèles météo actuelles utilisent des équations différentielles non linéaires et en gros, pour avoir des prédictions à peu près juste, on utilise un algorithme qui linéarise l'équation (je me rappelle plus du nom mais tu dois voir ce que je veux dire ) pour trouver des résultats et avec un super ordinateur, on calcule la fonction qu'on a choisi comme constante et plus l'ordinateur est puissant, plus les prévisions sont juste dans le temps. Si je te suis bien, un ordinateur quantique permettrait de grandement améliorer la météo...
 
sinon niveau simulation, je me rappelle quand j'étais plus jeune et que je jouais à Metal Gear Solid, le scientifique otacon utilisait des supers ordinateurs pour simuler l'explosion des charges nucléaires nouvelles génération ce qui était un peu mieux pour l'environnement que l'expérience Tsar bomba par exemple. Logiquement avec l'utilisation de la matière elle même pour créer de l'information numérique, on devrait avoir un résultat exact pour une telle expérience ?

Tu as compris l'essentiel.
Quelques détails : P c'est pas que linéaire, c'est tout ce qui se calcule en temps polynomial. Par exemple, en physique et en mécanique, on use et on abuse de modélisation par la méthode des éléments discrets. Et ce sont des trucs qui se calculent en temps polynomial (même si ça approxime des phénomènes non linéaires).
 
De plus une machine quantique ne permet pas de résoudre tous les problèmes NP. Seulement ceux qui appartiennent à BQP (qui sont une minorité).
 
Pour l'instant, l'immense majorité des choses qu'on simule ne gagne rien à être sur machine quantique. Il n'y a que certains phénomènes de physique quantiques dont la simulation appartient à la classe BQP.
 
Bref, Météo France ne tirerait certainement rien d'une machine quantique (a moins qu'on ne découvre de nouveaux algorithmes).

ok donc en gros c'est juste un fantasme de geek cette machine !

Un fantasme de cryptanalyste, surtout.  

Voilà un topik qu'il est intéressant    
 

 
A ce propos, je viens de lire ceci sur Wikipedia (article sur les Qubits) :  
 

 
En clair, cela signifierait que les ordinateurs quantiques ne sont pas plus puissants que leurs homologues "classiques" mais ne font que calculer de manière différente. Si ceci est bien exact, ça permet tout de même de relativiser la puissance de ces ordinateurs. Question : Peut-il exister des algos plus complexes à résoudre par un ordinateur quantique qu'avec un ordinateur classique ?

Bonne question. La réponse est non. C'est un modèle purement plus général.
 
BQP contient P.

 
ouep a priori il faudrait donc démultiplier les qubits pour réellement avoir une puissance de calcul bien supérieure.
Je pense à un truc au passage. Est ce qu'il n'y aurait pas un débouché dans le stockage ? vu qu'une particule peut être dans plusieurs états à la fois, on devrait pouvoir "ranger" beaucoup plus d'information d'un seul élements au lieu d'un unique bit de données. Amettons qu'un qubit puisse contenir 4 états superposés, alors une octet quantique contiendrait 24 élements d'information ce qui serait intéressant pour le stockage vu qu'on pourrait stocker beaucoup avec de bonnes performances... euh quoi que le souci vient de la lecture en fait, vu que dans le cas d'une paire de photons intriqués, si on mesure l'un l'autre disparait.

 
 
Oui, j'ai bien vu l"inclusion mais j'ai peut être mal posé la question en fait ! "BQP contient P" implique qu'un ordi quantique peut résoudre en temps polynomial tous les problèmes qu'un ordi classique peut aussi résoudre en temps polynomial. Par contre, est-ce le cas pour chaque problème.
 
Prenons un bête problème de tri de tableau par exemple (si je ne dis pas de bêtise) dont l'un des meilleurs algo est le tri-fusion (complexité en O(log2(n)) au pire des cas). Il se pourrait tout à fait qu'un ordi quantique ne possède pas d'algorithme aussi efficace pour effectuer un tri (bien que cet algo s'exécute en temps polynomial). On pourrait imaginer que le meilleur tri possible ne soit faisable qu'en O(n^3).
 
Ceci n'est bien sur qu'un exemple. Je n'ai pas regardé comment un tri pourrait être implémenté sur un ordi quantique. Si ce n'est pas vrai pour le problème du tri, c'est peut être vrai pour un autre problème sans contredire le fait que P est inclus dans BQP (à moins qu'il y ai déjà une démonstration de faite qui prouve le contraire !).
 
Pour le stockage, je n'en ai pas la moindre idée mais le coup de plusieurs états superposés, on le fait déjà à plus grande échelle sur les mémoires MLC des SSD.

Très juste. Je ne connais pas assez les modèles concrets pour répondre.
Si on veut jouer avec une machine quantique on a cet émulateur :
http://msc.phys.rug.nl/compphys0/QCE/doc/revqcs3.pdf
(évidemment, il met plus de temps à faire les calculs que ne le ferait une vrai machine quantique et il prend énormément de mémoire)
 

Oui, mais la mémoire MLC n'utilise pas des phénomènes quantiques. Même si un Qbit est la superposition de deux états, quand on le lit, on obtient seulement 0 ou 1 (sauf que la probabilité d'obtenir 0 ou 1 n'est pas égale)...

 
Thx, je vais y jeter un œil.
 

 
Bien sur , je disais ça par rapport à l'idée de superposer plusieurs états dans une même cellule pour gagner en place.

bonjour,
J'aurais quelques questions si vous le voulez bien ?
Si un qbit est fixé au moment de l'observation et pour toujours, comment régénère t- on l'espace d'adressage ?
On se déplace dans la matière ?
Question naïve c'est pour généraliser...
Si on veut calculer l'univers, une fois calculer, il ne pourra plus bouger ?
 
Un qbit observé, si il est fixe, il tombe par terre ou il disparait ?
Dans le cas contraire, observe-ton la matière ou l'espace ?

y a t'il un ingenieur de star trek dans la salle  ?  
 
drap