Si P = NP fuera cierto, ¿serían útiles las computadoras cuánticas?

29

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).

Philip White
fuente
9
No sabemos si implica B Q P = P , de modo que podría haber algún problema en B Q P que no esté en P incluso si P = N P ... Incluso es una pregunta abierta si o no B Q P está en P H ....P=NPBQP=PBQPPP=NPBQPPH
Tayfun Paga
44
Más básicamente, la clase captura algoritmos cuánticos "eficientes" (tiempo polinómico cuántico de error acotado). Es por eso que la formalización de su pregunta por parte de Tayfun es natural, por ejemplo, si P = N P , ¿todavía hay problemas en P , pero en B Q P ? Y aparentemente es consistente con nuestro conocimiento actual de que esto sucede. BQPP=NPPBQP
usul

Respuestas:

30

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.

Martin Schwarz
fuente
10
En realidad, el propio Aaronson demostró que la conjetura de que estaba basado en este trabajo es falsa. Ver scottaaronson.com/papers/glnfalse.pdf
Alex Grilo
55
@AlexGrilo Algunos de los resultados en el documento fueron incondicionales y aún se mantienen: existe una separación de oráculo entre las versiones relacionales de BQP y PH.
Sasho Nikolov
8
Una aclaración: mientras que la "Conjetura generalizada de Linial-Nisan" resultó ser falsa, la conjetura de que el problema de la Comprobación de Fourier / "Forrelation" no está en PH todavía se mantiene. Es solo que se necesitará algún otro enfoque para probarlo. Además, puedo fortalecer mi resultado de que existe un oráculo con respecto al cual existen problemas de relación BQP que no están en BPP ^ PH, para mostrar que existe un oráculo con respecto al cual P = NP, pero todavía hay problemas de relación BQP que no están en BPP . Es una extensión sencilla, pero desafortunadamente aún no la he escrito.
Scott Aaronson
9

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.

  1. La capacidad de consultar oráculos o bases de datos externas en superposición proporciona una separación comprobable entre las computadoras cuánticas y las computadoras clásicas en términos de complejidad de la consulta.
  2. Hay una variedad de tareas de comunicación que ven reducciones drásticas en el costo de comunicación que se utiliza la comunicación cuántica.
  3. El procesamiento cuántico de la información permite protocolos de información teóricamente seguros para una gama más amplia de problemas de los que son clásicamente posibles. Ciertamente, QKD no requiere que se implemente una computadora cuántica universal, pero sí muchos protocolos para otras tareas.
  4. El procesamiento previo y posterior de grandes estados cuánticos enredados le permite violar el límite de ruido de disparo en metrología, lo que resulta en mediciones más precisas.

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.

Joe Fitzsimons
fuente
4

Abordar la parte práctica.

P=NPO(n2103)

O(n1010000)

Hasta donde puedo decir, la computadora cuántica suficientemente potente será de interés práctico en este caso.

joro
fuente
n2103
@SashoNikolov me dirigí a la práctica . La computadora cuántica que factoriza enteros de 2048 bits de manera eficiente sería de interés práctico para mí a partir de ahora debido a las claves RSA;).
joro
Creo que uno puede obtener algoritmos de clasificación de tiempo lineal con computadoras cuánticas.
Baby Dragon
2

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#PBPPPH

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.

neófito
fuente