¿El problema P vs. NP se volvería trivial como resultado del desarrollo de computadoras cuánticas universales?

Si alguien construyera una computadora cuántica universal, ¿tendría alguna implicación en el problema de P vs. NP?

No, no habrá absolutamente ninguna implicación, por varias razones:

1. El problema P vs. NP se trata del cálculo clásico en lugar del cálculo cuántico. Incluso si las computadoras cuánticas pudieran resolver problemas difíciles de NP en tiempo polinómico (lo que no esperamos que puedan hacer), aún podría ser el caso de que las computadoras clásicas no puedan resolverlos en tiempo polinómico.

2. Las computadoras cuánticas universales, en un sentido teórico, son (según mi leal saber y entender) que ya existen. Estos son solo los análogos cuánticos de las máquinas universales de Turing: pueden ejecutar cualquier "programa" cuántico dado.

3. Tanto el cálculo cuántico como el problema P vs. NP son nociones teóricas. Lo que alguien puede construir en el mundo físico no tiene absolutamente nada que ver con nada que tenga que ver con ellos.

Lieuwe Vinkhuijzen dio una interpretación diferente de su pregunta:

¿Podrán las computadoras cuánticas resolver problemas NP-completos de manera eficiente?

La respuesta esperada es: no. Entonces, incluso en este sentido, las computadoras cuánticas físicas no nos permitirán resolver a voluntad los problemas de NP completo.

No se conocen implicaciones de ninguna manera: la simulación clásica de computadoras cuánticas no nos dice nada acerca de cuán difíciles son los problemas de búsqueda de NP; Las soluciones rápidas a los problemas de búsqueda de NP no nos dicen nada acerca de qué tan rápido se pueden simular clásicamente las computadoras cuánticas. Son posibles los siguientes escenarios:

• $P=NP=BQP$
• $P=NP\subsetneq BQP$
• $P\subsetneq NP=BQP$
• $P\subsetneq NP\subsetneq BQP$
• $P\subsetneq NP$ , pero y son incomparables$P\subsetneq BQP$$BQP$$NP$
• Los problemas de NP requieren fuerza bruta clásicamente, pero se resuelven mediante algoritmos cuánticos rápidos (aunque no necesariamente polinomiales)

El blog de un influyente científico teórico de la computación cuántica, Scott Aaronson, tiene el encabezado " Si toma solo una parte de la información de este blog: las computadoras cuánticas no resolverían problemas de búsqueda difíciles instantáneamente simplemente probando todas las soluciones a la vez ".

En un escenario (considerado improbable), construir una computadora cuántica universal tendría implicaciones en el problema de P vs. NP.

Esto se está expandiendo en el caso mencionado por Yuval Filmus, "si las computadoras cuánticas pudieran resolver problemas NP-duros en tiempo polinómico".

En tal situación, construir una computadora cuántica universal versus razonar teóricamente sobre una, tendría implicaciones para el problema P vs NP. Permitiría la posibilidad de simplemente usar computadoras cuánticas para buscar / encontrar una prueba que resuelva P vs NP, que luego podría ser verificada por una computadora clásica.

Sin embargo, como se mencionó en las otras respuestas, aunque no hay pruebas que separen BQP y NP-complete, actualmente la evidencia y las expectativas son que las computadoras cuánticas no podrán resolver problemas de NP-complete de manera eficiente.