Suponga que P = NP es verdadero. ¿Habría alguna aplicación práctica para construir una computadora cuántica, como resolver ciertos problemas más rápido, o cualquier mejora sería irrelevante debido al hecho de que P = NP es cierto? ¿Cómo caracterizaría la mejora en la eficiencia que se produciría si se pudiera construir una computadora cuántica en un mundo donde P = NP, en oposición a un mundo en el que P! = NP?
Aquí hay un ejemplo inventado de lo que estoy buscando:
Si P! = NP, vemos que la clase de complejidad ABC es igual a la clase de complejidad cuántica XYZ ... pero si P = NP, la clase ABC colapsa a la clase UVW relacionada de todos modos.
(Motivación: tengo curiosidad sobre esto, y relativamente nuevo en la computación cuántica; migre esta pregunta si no está lo suficientemente avanzada).
fuente
Respuestas:
El artículo " BQP y la Jerarquía Polinómica " de Scott Aaronson aborda directamente su pregunta. Si P = NP, entonces PH colapsaría. Si además BQP estuviera en PH, entonces no sería posible una aceleración cuántica en ese caso. Por otro lado, Aaronson da evidencia de un problema con la aceleración cuántica fuera del PH, por lo que tal aceleración sobreviviría a un colapso del PH.
fuente
La respuesta es un inequívoco sí. Las computadoras cuánticas definitivamente seguirían siendo útiles.
Las computadoras cuánticas no son oráculos para BQP, sino dispositivos que procesan estados cuánticos y pueden comunicarse utilizando estados cuánticos. Así como la capacidad de realizar consultas no deterministas es fundamentalmente más poderosa que la capacidad de realizar consultas puramente deterministas, independientemente del estado de P frente a NP (y de hecho esta es la raíz de las separaciones de oráculo), la capacidad de realizar consultas cuánticas y comunicarse usando estados cuánticos es fundamentalmente más poderoso que el equivalente puramente clásico.
Esto conlleva ventajas en una amplia gama de aplicaciones.
Aparte de los argumentos de complejidad, hay otra razón práctica para querer computadoras cuánticas. Gran parte de los datos procesados en las computadoras clásicas en estos días se derivan de la percepción del mundo natural (por ejemplo, a través del CCD en una cámara digital). Sin embargo, tales mediciones necesariamente arrojan cierta información sobre el sistema para representar el resultado de la medición como una cadena de bits clásica (por ejemplo, colapso de superposiciones espaciales de fotones), y no siempre está claro qué información se considerará más importante cuando inicialmente registrando los datos. Por lo tanto, es razonable creer que la capacidad de almacenar y procesar estados cuánticos directamente, en lugar de colapsarlos de alguna manera antes del procesamiento, será cada vez más deseable.
fuente
Abordar la parte práctica.
Hasta donde puedo decir, la computadora cuántica suficientemente potente será de interés práctico en este caso.
fuente
Existen estudios sobre la relación entre BQP y la jerarquía polinómica PH. Por ejemplo, hay un problema relativo al que BQP no está contenido en PH ( http://arxiv.org/abs/0910.4698 ), y una conjetura que demuestra el mismo resultado en un mundo no relativizado ( http://arxiv.org /abs/1007.0305P#P⊆BPPPH
En conclusión, no sabemos cuál es el poder exacto de las computadoras cuánticas, pero hay resultados que sugieren que BQP podría estar fuera del PH.
fuente