Est-il prouvé que le calcul quantique ne résout pas mieux les problèmes complets de NP que le calcul classique?

14

Est-il prouvé que le calcul quantique ne résout pas mieux les problèmes complets de NP que le calcul classique ou on le croit simplement?

np-complete quantum-computing kptlronyttcna
la source

Réponses:

11

On soupçonne que les problèmes NP-complets ne peuvent pas être résolus en temps polynomial quantique (c'est-à-dire qu'ils ne sont pas en BQP), mais cela n'a pas été prouvé. Nous ne nous attendons pas à une preuve dans un avenir proche, car cela impliquerait que P est différent de NP.

Yuval Filmus
la source
3
Et l'inverse. Si NP-complet se révèle être en BQP, cela signifie-t-il quelque chose à propos de P vs NP?
kptlronyttcna
1
Rien n'était connu en 2007 , mais c'était il y a un certain temps déjà.
Yuval Filmus
1
@kptlronyttcna Je pense que cela ne dirait rien sur P vs NP car P vs BQP n'est pas encore établi.
P.Péter