Les problème comme la factorisation de grand nombres sont de classe de complexité NP (Non-deterministic Polynomial), c'est à dire que pour les résoudre il faut un temps polynomial en fonction de la taille des entrées. (c'est à dire relativement rapide) sur une machine non déterministe.
Le problème c'est que des machine non déterministe en pratique ça n'existe pas, c'est juste une théorie. Il faut en émuler sur des machine normale en refaisant le même calcul sur toutes les possibilités, ce qui prend un temps exponentiel par rapport à la taille des données (ce qui est très lent)
Par contre, l'ordinateur quantique en serait une machine non déterministe.
Le principe de l'ordinateur quantique est que les qubits sont dans plusieurs états simultanément, avec des probabilités différente. Le but d'un algorithme quantique est d'agir sur les qubits afin de rendre la probabilité que les qubits indiquent ce qu'on cherche grande, et la probabilité que les qubits indiquent une réponse erronée tendant vers zéro.
Mais une fois qu'on observera les qubits, on observera qu'un seul état qui sera la bonne réponse avec une forte probabilité.
[^] # Re: C'est pas nouveau
Posté par Gof (site web personnel) . En réponse au journal Calcul quantique. Évalué à 7.
Le problème c'est que des machine non déterministe en pratique ça n'existe pas, c'est juste une théorie. Il faut en émuler sur des machine normale en refaisant le même calcul sur toutes les possibilités, ce qui prend un temps exponentiel par rapport à la taille des données (ce qui est très lent)
Par contre, l'ordinateur quantique en serait une machine non déterministe.
Le principe de l'ordinateur quantique est que les qubits sont dans plusieurs états simultanément, avec des probabilités différente. Le but d'un algorithme quantique est d'agir sur les qubits afin de rendre la probabilité que les qubits indiquent ce qu'on cherche grande, et la probabilité que les qubits indiquent une réponse erronée tendant vers zéro.
Mais une fois qu'on observera les qubits, on observera qu'un seul état qui sera la bonne réponse avec une forte probabilité.