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?
fuente
Respuestas:
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.
fuente