Envoyé par
Thorms
Est-ce que les ordinateurs quantiques permettent de résoudre des problèmes que l'on ne peut pas résoudre avec un ordinateur classique ?
D'un point de vue strictement fonctionnel, un ordinateur quantique ne permet pas de faire plus qu'un ordinateur classique.
En chipotant on pourrait même dire qu'il fait moins bien (toujours d'un point de vue strictement fonctionnel) puisque les résultats obtenus ne sont les résultats recherchés que dans une certaine probabilité.
Pour être précis, ce n'est pas l'algorithme lui-même qui est source d'erreur mais la lecture (la
mesure, dirait un physicien) du résultat. En physique classique on peut lire une mémoire sans la modifier significativement. En physique quantique, une mesure modifie l'état. Un qbit ne vaut pas 1 ou 0 mais vaut "1 avec un probabilité p" et "0 avec un probabilité 1-p". C'est en exploitant cela qu'on fait la superposition quantique. Mais la mesure va projeter ce q-bit sur "1" ou "0" selon la probabilité p. Donc, non seulement on perd la valeur quantique superposée définitivement, mais on ne peut pas prédire à l'avance le résultat qui sera lu.
Le principe de base de l'algorithmique quantique étant de faire diminuer la probabilité d'erreur, généralement en répétant une même opération en boucle, la probabilité d'erreur diminuant à chaque pas. Le résultat d'un algorithme quantique est finalement passé à un algorithme classique pour vérifier que le résultat obtenu est correct.
Globalement ce processus est en fait intéressant car grâce à la superposition quantique, un algo quantique va résoudre en temps polynomial un problème de complexité exponentiel en algo classique. Généralement la vérification que le résultat obtenu est correct se fait en temps polynomial (cf les
problèmes NP-complets par exemple).
Le processus global passe donc d'une complexité exponentielle à une complexité polynomiale. Mais on ne gagne rien d'un point de vue strictement fonctionnel.
Il existe aussi des contraintes structurelles dans un ordinateur quantique: par exemple l'opération de "copie" n'existe pas, on ne peut pas copier à l’identique une "q-valeur" (à cause de la
mesure qui détruit la valeur). En revanche, l’opération "échange" existe physiquement alors qu'elle nécessite 3 opérations de copie et l'utilisation d'un 3ème emplacement temporaire en algo classique (t <- a; a <- b; b <- t). On ne peut pas "copier" mais on peut donc quand même "déplacer".
Evidemment entre ce qui est possible d'un point de vue théorique et ce qu'on est capable de faire en réalité est un autre problème. Outre les problèmes physiques qu'on va laisser aux physiciens, il y a aussi pour nous le fait d'être capable d'écrire des programmes quantiques et d'avoir des langages pour le faire.
Voilà un peu l'essentiel de ce que j'ai retenu de mes cours d'informatique quantique pendant mes études.
A la fin de mes études j'avais postulé pour faire une thèse qui consistait à créer un langage pour la programmation quantique, c'est quelqu'un d'autre qui a été pris et j'ai finalement fait une thèse sur les méthodes formelles mais forcément je vais aller jeter un coup d’œil pour voir ce que google nous propose comme langage. D'ailleurs on est dans un cas flagrant où les méthodes formelles peuvent s'avérer extrêmement utile pour vérifier et étudier des algorithmes quantiques puisque pas grand monde n'a un ordinateur quantique sous la main pour tester ses programmes... J'arrête cette digression personnelle.
Je pense que l'intérêt de google en mettant à disposition cet outils est de voir (et récupérer) les algorithmes que les utilisateurs vont proposés.
D'un point de vue calculatoire, le principal intérêt d'un ordinateur quantique est le gain de vitesse, donc, par définition, on ne peut pas simuler de façon satisfaisante un ordinateur quantique sur un ordinateur classique. Il ne faudra pas s'attendre à des miracles sur cet outil. Mais ça peut sans doute être très bien pour découvrir, s’exercer et faire progresser les connaissances en algorithmes quantiques (il n'y a pas grand-chose pour le moment, presque tout reste à inventer) en attendant les ordinateurs eux-mêmes soient au point.
Envoyé par
Arsene Newman
Pensez-vous que le calculateur quantique représente la prochaine révolution de l’informatique ?
Oui, en fait le doute ne me traverse même pas.
D'une part on a le gain d'échelle sur les temps de calculs. Il y a aussi les possibilités de miniaturisations envisageables. En fait déjà aujourd'hui avec la miniaturisation des processeurs on est arrivé au niveau où il faut gérer les effets quantiques. Donc de toute façon autant en tirer parti autant que possible plutôt que de chercher à les éviter. Même si dans un premier temps on n'aura sans doute pas encore de vrais ordinateurs quantiques.
Plus encore, c'est une vision tout à fait personnelle, je trouve qu'architecturalement les ordinateurs quantique sont plus proches des réseaux de neurones ou des réseaux bayésiens que de l'architecture d'un ordinateur classique. Compte tenu de l'impossibilité de faire des copies et de lire une valeur sans la détruire, je ne suis pas certain qu'il y ait un grand intérêt (je serai peut-être démenti) à avoir une mémoire centrale d'un côté et une unité de calcul de l'autre. J'imagine plutôt des unités de calculs relativement réduite reliées en réseau.
Cet aspect "réseau" (peut-être un pur fantasme de ma part), l'aspect probabiliste des résultats et les gains en échelle de temps, me font penser que les ordinateurs quantiques seront parfaits pour faire tourner des algorithmes de prévision, de décision ou faire de l'intelligence artificielle. Compte tenu des enjeux économiques dans ces domaines, je pense donc qu'il n'y aura aucun problème pour trouver les investisseurs pour financer tout ça.
18 |
0 |
Vous avez sans doute déjà entendu parler d’ordinateur ou de calculateur quantique, cet outil de calcul très puissant en mesure de résoudre les problèmes algorithmiques les plus complexes, en se basant sur le principe de la superposition d’états quantiques et sur les équivalents des bits actuels : les qubits.
) : alors oui ce sera possible.