¿Está comprobado que el cálculo cuántico no es mejor para resolver problemas completos de NP que el cálculo clásico?

14

¿Está comprobado que el cálculo cuántico no es mejor para resolver problemas completos de NP que el cálculo clásico o simplemente se cree?

np-complete quantum-computing kptlronyttcna
fuente

Respuestas:

11

Se sospecha que los problemas de NP completo no se pueden resolver en el tiempo polinómico cuántico (es decir, que no están en BQP), pero esto no se ha demostrado. No esperamos una prueba en el futuro cercano, ya que esto implicaría que P es diferente de NP.

Yuval Filmus
fuente
3
Qué acerca del otro camino alrededor. Si se demuestra que NP-complete está en BQP, ¿eso dice algo sobre P vs NP?
kptlronyttcna
1
No se sabía nada en 2007 , aunque eso fue hace bastante tiempo.
Yuval Filmus
1
@kptlronyttcna Creo que no diría nada sobre P vs NP ya que P vs BQP tampoco está establecido todavía.
P.Péter