¿Hay resultados de algoritmos cuánticos o complejidad que conduzcan a avances en el problema P vs NP?

14

En la superficie, los algoritmos cuánticos tienen poco que ver con la informática clásica y P vs NP en particular: la resolución de problemas de NP con computadoras cuánticas no nos dice nada sobre las relaciones de estas clases de complejidad clásicas 1 .

Por otro lado, la 'descripción alternativa' de la clase de complejidad clásica PP como la clase PostBQP presentada en este documento es, hasta donde sé, considerado como un resultado importante para la 'complejidad clásica', por 'complejidad cuántica' .

De hecho, Scott Aaronson, el autor del artículo, escribe al final del resumen:

Esto ilustra que la computación cuántica puede proporcionar pruebas nuevas y más simples de resultados importantes sobre la computación clásica.


Por lo tanto, mi pregunta es: ¿existen resultados del campo de la complejidad cuántica que 'simplifiquen' el problema P vs NP, similar a la descripción cuántica de PP? Si no hay tales resultados, ¿hay una buena razón para no esperar estos resultados, a pesar del "éxito" de PP?

1: Tome la respuesta a esta pregunta, por ejemplo: ¿El problema P vs. NP se volvería trivial como resultado del desarrollo de computadoras cuánticas universales?

Lagarto discreto
fuente
Buena pregunta, también estoy muy interesado en este tema en particular. ¡Gracias!
SalvaCardona

Respuestas:

9

No creo que haya razones claras para una respuesta de 'sí' o 'no'. Sin embargo, puedo proporcionar una razón por la cual PP era mucho más probable que admitiera tal caracterización que NP , y dar algunas intuiciones de por qué NP podría nunca tener una caracterización simple en términos de modificación del modelo computacional cuántico.

Complejidad de conteo

Las clases NP y PP pueden caracterizarse en términos del número de ramas de aceptación de una máquina de Turing no determinista, que podemos describir de una manera más realista en términos de los posibles resultados de un cálculo aleatorio que utiliza bits uniformemente al azar. Luego podemos describir estas dos clases como:

  • L  ∈  NP si hay un algoritmo aleatorio de tiempo polinómico que genera un solo bit α  ∈ {0,1}, de modo que x  ∈  L si y solo si Prα  = 1 | x  ] no es cero (aunque esta probabilidad puede ser pequeña), a diferencia de cero.

  • L  ∈  PP si hay un algoritmo aleatorio de tiempo polinómico que genera un solo bit α  ∈ {0,1}, de modo que x  ∈  L si y solo si Prα  = 1 | x  ] es mayor que 0.5 (aunque posiblemente solo por la cantidad más  pequeña ), en lugar de ser igual o menor a 0.5 ( por ejemplo, por una pequeña cantidad).

Una forma de ver por qué estas clases no pueden resolverse prácticamente utilizando esta descripción probabilística es que puede tomar exponencialmente muchas repeticiones para confiar en una estimación de probabilidad para Prα  = 1 | x  ] debido a la pequeñez de las diferencias en las probabilidades involucradas.

Complejidad de brecha y complejidad cuántica

Describamos los resultados '0' y '1' en el cálculo anterior como 'rechazar' y 'aceptar'; y llamemos a una rama aleatoria que da un resultado de rechazo / aceptación, una rama de rechazo o aceptación . Debido a que cada rama del cómputo aleatorizado que no acepta es, por lo tanto, rechaza, PP también se puede definir en términos de la diferencia entre el número de rutas computacionales de aceptación y rechazo, una cantidad que podemos llamar la brecha de aceptación : específicamente, si la aceptación La brecha es positiva, o menor o igual que cero. Con un poco más de trabajo, podemos obtener una caracterización equivalente para PP, en términos de si la brecha de aceptación es mayor que algún umbral, o menor que algún umbral, que puede ser cero o cualquier otra función eficientemente computable de la entrada x .

Esto a su vez se puede utilizar para caracterizar idiomas en PP en términos de cálculo cuántico. A partir de la descripción de PP en términos de cálculos aleatorios que tienen probabilidades de aceptación (posiblemente ligeramente) mayores que 0.5, o como máximo 0.5, todos los problemas en PP admiten un algoritmo cuántico de tiempo polinómico que tiene la misma distinción en probabilidades de aceptación; y al modelar cálculos cuánticos como una suma sobre rutas computacionales, y simular estas rutas usando ramas de rechazo para rutas de peso negativo y aceptar ramas de rutas de peso positivo, también podemos mostrar que un algoritmo cuántico que hace una distinción (estadísticamente débil) describe Un problema en PP .

No es obvio que podamos hacer lo mismo para NP . No hay una forma natural de describir NP en términos de brechas de aceptación, y la suposición obvia de cómo podría tratar de encajarlo en el modelo computacional cuántico, preguntando si la probabilidad de medir un resultado '1' es cero o no cero: en cambio, le da una clase llamada coC = P , que no se sabe que es igual a NP , y más o menos podría describirse como tan potente como PP en lugar de cerca de NP en potencia.

Por supuesto, algún día uno podría encontrar de alguna manera una caracterización de NP en términos de brechas de aceptación, o podría encontrar nuevas formas de relacionar la computación cuántica con la complejidad del conteo, pero no estoy seguro de que alguien tenga alguna idea convincente de cómo podría ocurrir esto.

Resumen

Las perspectivas de obtener información sobre el problema P versus NP en sí, a través del cálculo cuántico, no son prometedoras, aunque no es imposible.

Niel de Beaudrap
fuente
3
Respuesta impresionante! Me parece que aunque la computación cuántica en sí misma podría no ayudar, la intuición y las matemáticas de la complejidad cuántica son terriblemente similares a los enfoques geométricos y aritméticos del problema P vs. NP. Véase, por ejemplo, el artículo reciente sobre politopos de momento: algoritmos eficientes para la escala del tensor, márgenes cuánticos y politopos de momento. Además, no puedo mencionar uno de mis artículos favoritos aquí: Pruebas cuánticas para teoremas clásicos de Andrew Drucker y Ronald de Wolf .
Sanketh Menda