Une très grosse différence, c'est que travailler sur des qbits revient à travailler sur toutes les combinaisons possibles en même temps: donc avec 2 Qb, on manipule 4 configurations en même temps, avec 3 => 8
4 => 16
10 => environ 1000
100 => environ 100000000000000000000000000000 0000
Il y a peut-être d'autres différences permettant l'hypercomputation (aller au delà des machines de Turing), mais c'est pas très clair pour moi.
Envoyé par Jiav
Pour moi non plus. As - tu un peu creusé le sujet depuis nos dernières discussions ?
Comment déduis-tu ca stp?En fait je ne vois pas vraiment l'utiliter de travailleur sur tous ces états en même temps... Lors d'un calcule ne doit-on pas manipuler des bits spécifiques? Ou peut être dois je raisonner par rapport aux algorithmes (de shor par exemple) élaborés pour utiliser ce parallèlisme? Comment marchent-ils?
Avant de parler de l'algo de shor, on peut essayer de discuter des algos quantiques plus simples.
L'algorithme de Deutsch est l'un des plus abordables. Il permet de savoir si les valeurs f(0) et f(1) d'une fonction sont égales ou non (avec f(x) = 0 ou 1 )
D'un point de vue classique avec un processeur qui exécute des séquences d'opérations, on a l'algo suivant :
1/ calculer f(0)
2/ calculer f(1)
3/ comparer f(0) et f(1)
3 instructions au moins. Avec l'algo de Deutsch, c'est réalisé en une seule opération.
En gros, on imagine un système quantique qui engendre un état quantique de la forme
Une mesure réalisée sur cet état répond immédiatement à la question f(0) = f(1) ou f(0) différent de f(1).
Si tu obtiens l'état |0> les deux valeurs sont égales, si tu obtiens |1> elles sont différentes.
C'est un exemple extrêmement basique et inutile, mais il illustre bien la différence de logique entre la conception d'un algo classique et d'un algo quantique. Classiquement on explicite les quantités à étudier, en quantique on construit une combinaison linéaire de q-bits qui contient l'information nécessaire à la résolution du problème.
Dernière modification par spi100 ; 26/10/2005 à 22h38.
J'ai bien du mal... pas assez de connaissance en physique quantique pour être sur de bien comprendre le papiers. Faudrait que je fasse une formation mais outch!
Je ne fais que transmettre ce que j'ai compris
Moi oui! Il y a certains problèmes qui nécessitent un temps exponentiel pour être calculés (factoriser un nombre, trier une base de donnée, problème du voyageur de commerce). Autrement dit, en pratique ils sont irrésolvables. En utilisant du calcul quantique, ce type de problème redevient résolvable en temps raisonable.
Personnellement, une application que je voudrais c'est "soit un réseau de neurone de n éléments, organisés comme ci, quels sont les solutions possibles (en terme de distribution de poids synaptiques) qui donneraient une activité compatible avec tel et tel enregistrement EEG?". Le problème est irrésolvable en temps raisonable par un ordi classique (bien trop de possibilités!). Par contre un ordinateur quantique pourrait tester toutes les possibilités en même temps et ainsi donner des réponses intéressantes. Sans aller jusqu'à imaginer avoir un réponse exacte (une seule solution possible), on pourrait imaginer avoir une réponse à: parmi tous les modèles possibles, quelle est la probabilité que telle aire préfrontal soit connectée à telle aire pariétale? Voyez le genre?
En fait je pense avoir lu des choses qui vont un peu dans le sens de ce que tu dis, dans Le Bellac d'informatique quantique.
Il y a une autre version de la thèse de Church Turing qui est aussi qualifiée de forte qui dit que tout problème algorithmique est dans la classe P. Dans cette hypothèse, les problèmes qui sont réputés NP, ne le seraient pas (simplement nous ne connaitrions pas d'algos efficaces pour le pb).
Dans la mesure où la conjecture P différent de NP est encore ouverte, cette thèse forte reste possible.
Les algorithmes quantiques montrent qu'un problème réputé NP comme la factorisation d'un nombre en facteurs premiers, passe dans P avec l'algo de Shor. C'est peut-être de là que vient l'idée que les algo quantiques sont plus puissants.
Pour n'importe quel problème algorithmique dans P, tu peux inventer un algorithme très mauvais, et qui converge extrêmement lentements. Montrer qu'il est possible de formuler des algo qui convergent plus rapidement en Informatique quantique, ne veut pas dire forcemment que l'on est capable de résoudre le halting problème, mais juste que l'on a formulé un algo plus efficace.
En résumé, il faut bien différencier la thèse de Church-Turing de la thèse de Church-Turing forte. La première est une définition de la calculabilité, la seconde fait intervenir des notions d'efficacité d'algorithme.
Les affirmations que les ordinateurs quantiques sont plus puissants, se fondent sur la deuxième thèse. Dans la mesure où personne ne sait si 'P différent de NP', il faut prendre cette affirmation avec tous les bémols nécessaires.
Dernière modification par spi100 ; 27/10/2005 à 09h19.
Je ne savais pas que P inégal NP n'était qu'une conjecture, sinon tout à fait ok pour le reste. Au passage merci pour la ref Le Bellac! Par contre même s'il advenait que P=NP soit démontré, en pratique il faudrait aussi une méthode de transformation des NP en P. D'ici là l'ordinateur quantique sera toujours aussi attractif
Oui, bien sûr. Il est probable que si ce devait être le cas, les problèmes prétendus NP auraient des exposants assez grands. Par exemple, le problème de savoir si un nombre X est premier, était réputé NP jusqu'à ces deux dernières années. Je crois me souvenir, que l'algorithme trouvé est quand même enJe ne savais pas que P inégal NP n'était qu'une conjecture, sinon tout à fait ok pour le reste. Au passage merci pour la ref Le Bellac! Par contre même s'il advenait que P=NP soit démontré, en pratique il faudrait aussi une méthode de transformation des NP en P. D'ici là l'ordinateur quantique sera toujours aussi attractiftandis que les problèmes réputés P ne sont généralement pas au dessus de
C'est plus le cas?? Je suis sur le *** Aurais-tu une ref STP?Par exemple, le problème de savoir si un nombre X est premier, était réputé NP jusqu'à ces deux dernières années.
Oui, c'est l'algorithme AKS, l'article correspondant a un titre qui sonne bien : "Prime is in P". En le tapant dans google tu trouveras pas mal d'infos dessus, j'y ai vu ça http://www.mcs.sdsmt.edu/~ecorwin/cr...rimes_in_p.ppt
Cet algo en lui même n'est pas performant du tout, il l'est moins que les méthodes probabilistes en tout cas. Mais quand même, c'est le premier de classe P qui soit exhibé.
Merci! Plein de choses intéressantes
