On sait déjà que les problèmes NP-complets restent difficile même en quantique
Pour être plus exact, on n'en sait rien. Ça a l'air d'être le cas, mais pas de preuve pour l'instant. Et pour cause, le montrer reviendrait à montrer que P est différent de NP. En fait, même en supposant que P est différent de NP, la question reste ouverte.
La seule chose que l'on peut dire c'est qu'à l'heure actuelle on a un algorithme quantique efficace pour la factorisation et aucun algorithme classique efficace.
[^] # Re: Peut-être même à 6 chiffres !
Posté par Sarcastic . En réponse au journal [Quantique] La ligne des 49 qubits. Évalué à 2.
Pour être plus exact, on n'en sait rien. Ça a l'air d'être le cas, mais pas de preuve pour l'instant. Et pour cause, le montrer reviendrait à montrer que P est différent de NP. En fait, même en supposant que P est différent de NP, la question reste ouverte.
La seule chose que l'on peut dire c'est qu'à l'heure actuelle on a un algorithme quantique efficace pour la factorisation et aucun algorithme classique efficace.