En parlant d’ordinateurs quantiques, je ne sais pas si tu voulais dire qu’un ordinateur quantique peut résoudre un problème NP en temps polynomial, mais ce n’est absolument pas sûr.
En fait, pour les ordinateurs quantiques, il y a le même genre de problèmes que pour P et NP, mais en ce qui concerne la classe en:BQP (bounded-error quantum polynomial time, la classe des problèmes solubles en temps polynomial par un ordinateur quantique avec une erreur arbitrairement faible).
Par exemple, on sait que la factorisation de nombre premiers est dans BQP (grâce au fameux algorithme de Shor), mais comme il n’est pas prouvé que ce problème de factorisation n’est pas dans P, cela ne prouve pas que BQP est strictement plus grand que P.
En l’état actuel, on peut juste affirmer qu’on connaît un algorithme efficace pour factoriser des nombres premiers sur un ordinateur quantique, et pas sur un ordinateur classique.
[^] # Re: Mais ké kidi?
Posté par micha_mosk . En réponse au journal P != NP : la preuve. Évalué à 6.
En fait, pour les ordinateurs quantiques, il y a le même genre de problèmes que pour P et NP, mais en ce qui concerne la classe en:BQP (bounded-error quantum polynomial time, la classe des problèmes solubles en temps polynomial par un ordinateur quantique avec une erreur arbitrairement faible).
Par exemple, on sait que la factorisation de nombre premiers est dans BQP (grâce au fameux algorithme de Shor), mais comme il n’est pas prouvé que ce problème de factorisation n’est pas dans P, cela ne prouve pas que BQP est strictement plus grand que P.
En l’état actuel, on peut juste affirmer qu’on connaît un algorithme efficace pour factoriser des nombres premiers sur un ordinateur quantique, et pas sur un ordinateur classique.