Este ha sido un importante problema abierto en la teoría de la complejidad cuántica durante 20 años. Esto es lo que sabemos:
(1) Supongamos que se insiste en hablar sólo de problemas de decisión (los "totales", que tienen que definirse para cada entrada), como hace tradicionalmente la gente cuando define clases de complejidad como P, NP y BQP. Entonces tenemos separaciones probadas entre BQP y NP en el "modelo de caja negra" (es decir, el modelo en el que tanto la máquina BQP como la máquina NP tienen acceso a un oráculo), como aludió mmc. Por otro lado, aunque es muy plausible que se extiendan a separaciones de oráculo entre BQP y PH (toda la jerarquía polinómica), ahora mismo ni siquiera sabemos cómo demostrar una separación de oráculo entre BQP y AM (una generalización probabilística de NP ligeramente superior a MA). A grandes rasgos, lo mejor que podemos hacer es separar BQP de MA.
Y para reiterar, todas estas separaciones son sólo en el modelo de caja negra. Sigue sin estar completamente claro, incluso a nivel de conjetura, si se traducen o no en separaciones en el mundo "real" (es decir, el mundo sin oráculos). No tenemos ningún ejemplo claro análogo a la factorización, de problemas de decisión reales en BQP que plausiblemente no estén en NP. Después de años pensando en el problema, todavía no tengo una intuición fuerte ni de que BQP debería estar contenido en NP en el mundo "real" ni de que no debería estarlo.
(Nota añadida: Si se permiten los "problemas de promesa", término de los informáticos para los problemas cuyas respuestas pueden ser indefinidas para algunas entradas, entonces supongo que hay probablemente es efectivamente una separación entre PromiseBQP y PromiseNP. Pero mi ejemplo, que supongo que es testigo de la separación, es sólo el tautológico. Es decir, "dado como entrada un circuito cuántico, ¿este circuito da como resultado SÍ con al menos el 90% de probabilidad o con al menos el 10% de probabilidad, prometiendo que uno de esos es el caso?")
Para más información, consulte mi artículo BQP y la jerarquía polinómica .
(2) Por otro lado, si estás dispuesto a generalizar tu noción de "problema computacional" más allá de los problemas de decisión -por ejemplo, a los problemas de muestreo a partir de una distribución de probabilidad específica-, la situación se vuelve mucho más clara. En primer lugar, como dijo Niel de Beaudrap, Alex Arkhipov y yo (e independientemente, Bremner, Jozsa y Shepherd ) demostró que hay problemas de muestreo en BQP (OK, técnicamente, "SampBQP") que no pueden estar en NP, o de hecho en cualquier parte de la jerarquía de polinomios, sin que la jerarquía se colapse. En segundo lugar, en mi artículo BQP vs. PH enlazado anteriormente, demostré incondicionalmente que en relación con un al azar oráculo, hay problemas de muestreo y búsqueda en BQP que no están en ninguna parte de PH, y mucho menos en NP. Y a diferencia de los oráculos "raros y especiales" necesarios para las separaciones del punto (1), los oráculos aleatorios se pueden "instanciar físicamente" -por ejemplo, utilizando cualquier función pseudoaleatoria criptográfica-, en cuyo caso estas separaciones se trasladarían de forma muy plausible al mundo "real" sin oráculos.
