vs?

El problema central de la teoría de la complejidad es posiblemente vs .$P$$NP$

Sin embargo, dado que la naturaleza es cuántica, parecería más natural considerar las clases (es decir, problemas de decisión que una computadora cuántica puede resolver en tiempo polinómico, con una probabilidad de error de 1/3 como máximo para todas las instancias) y (el equivalente cuántico de ) en su lugar.$BQP$$QMA$$NP$

Mis preguntas:

1) ¿Una solución al problema vs daría una solución a vs ?$P$$NP$$BQP$$QMA$

2) ¿Las tres barreras de relativización, pruebas naturales y algebrización también se aplican al problema vs ?$BQP$$QMA$

1) No se conoce implicación en ninguna dirección. Sabemos que P = NP implica P = PH. Pero no sabemos si BQP y QMA están en PH, por lo que tal vez P podría ser igual a NP pero BQP y QMA aún no colapsarían. (Por otro lado, tenga en cuenta que QMA⊆PP⊆P ^#P , por lo que ciertamente P = P ^#P implicaría BQP = QMA.) Mostrar que BQP = QMA implica P = NP parece aún más desesperado en el estado actual del conocimiento .

2) Absolutamente, las tres barreras se aplican con toda su fuerza a BQP vs. QMA (e incluso al problema "más fácil" de probar P ≠ PSPACE). Primero, en relación con un oráculo PSPACE (o incluso la extensión de bajo grado de un oráculo PSPACE), tenemos

P = NP = BQP = QMA = PSPACE,

ciertamente, se necesitarán técnicas no relativizantes y no algebrizantes para separar cualquiera de estas clases. En segundo lugar, para obtener una barrera de pruebas naturales para colocar cosas fuera de BQP, todo lo que necesita es una familia de funciones pseudoaleatoria que sea computable en BQP, que es un requisito formalmente más débil que una familia de funciones pseudoaleatoria computable en P.

Anexo: Permítanme decir algo acerca de una "meta pregunta" que no preguntó pero insinuó, por qué la gente todavía se enfoca en P vs. NP a pesar de que creemos que la Naturaleza es cuántica. Personalmente, siempre he visto P vs. NP como nada más que el "buque insignia" para un montón de preguntas de barrera en la teoría de la complejidad (P vs. PSPACE, P vs. BQP, NP vs. coNP, NP vs. BQP, la existencia de funciones unidireccionales, etc.), ningunade los cuales sabemos cómo responder, y todos los cuales están relacionados en el sentido de que cualquier avance con uno muy probablemente conduciría a avances con los otros (incluso cuando no tenemos implicaciones formales entre las preguntas, que en muchos casos hacer). P vs. NP no es inherentemente más fundamental que cualquiera de los otros, pero si tenemos que elegir una pregunta para que sirva como elemento secundario para la complejidad, entonces es una buena elección.