Pregunta:
En primer lugar, me sorprende un poco que no haya podido encontrar ningún documento / artículo que defina tal jerarquía.
Puede definirse de la siguiente manera:
$ \ Delta_0 ^ {\ mathsf {BQP}} = \ Sigma_0 ^ {\ mathsf {BQP}} = \ Pi_0 ^ {\ mathsf {BQP}} = \ Delta_1 ^ {\ mathsf {BQP}} \ mathsf {= BQP} PS
$ \ Delta_k ^ {\ mathsf {BQP}} = \ mathsf {BQP} ^ {\ Sigma_ {k-1} ^ {\ mathsf {BQP}}} $
$ \ Sigma_k ^ {\ mathsf {BQP}} = \ mathsf {QMA} ^ {\ Sigma_ {k-1} ^ {\ mathsf {BQP}}} $
$ \ Pi_k ^ {\ mathsf {BQP}} = \ mathsf {coQMA} ^ {\ Sigma_ {k-1} ^ {\ mathsf {BQP}}} $
¿Se sabe que toda esta jerarquía está contenida en algún nivel finito de jerarquía de conteo como $ \ mathsf {PH} $ (que está contenido en el segundo nivel de jerarquía de conteo, $ \ mathsf {P ^ {PP}} $)? Si no es así, ¿hay alguna expectativa al respecto?
Respuesta:
También me sorprendió bastante no encontrar esta jerarquía en la literatura, así que escribí mi tesis de posgrado al respecto. Estará disponible en línea pronto, momento en el que actualizaré esta respuesta con un enlace. Pude demostrar algunos teoremas interesantes al respecto.
Teorema Para cada $ i $, $ \ Sigma_i ^ {\ mathsf {BQP}} \ subseteq C_i ^ \ mathsf {P} $, donde $ C_i ^ \ mathsf {P} $ es el $ i $ -ésimo nivel del conteo jerarquía. Entonces, toda la jerarquía está contenida en la jerarquía de conteo.
Prueba trivialmente de $ QMA \ subseteq PP $. $ \ cuadrado $
Teorema Si $ \ Delta_i ^ {BQP} = \ Sigma_i ^ {BQP} $ entonces $ BQPH = \ Delta_i ^ {BQP} $.
Prueba de ejercicio para el lector.
Teorema Si $ QMA = PP $ entonces $ PH \ subseteq QMA $ y de hecho $ PH ^ {PP} = QMA $.
La primera parte de este teorema fue originalmente de Vyalyi [4], pero su demostración son seis páginas de álgebra, mientras que las nuevas ideas que se originaron al pensar en su jerarquía me permiten llegar allí en solo unas pocas líneas:
Prueba Demuestro un nuevo teorema: $ QMA \ cap coQMA = P ^ {QMA \ cap coQMA} $. Esto nos da $ QMA = P ^ {QMA} = P ^ {PP} \ supseteq PH $ por Toda. $ \ cuadrado $
Para la parte nueva, $ PH ^ {PP} = QMA $, tendrás que leer mi tesis. No hay un análogo obvio del teorema de Toda. La razón es que el ingrediente crítico $ QMA \ subseteq BPP ^ {\ oplus P} $ parece difícil en el caso cuántico, mientras que clásicamente $ NP \ subseteq BPP ^ {\ oplus P} $ se sigue trivialmente de Valiant-Vazirani, porque aquí no tengo una forma de "contar" las soluciones. Incluso si toma $ QCMA $ en lugar de $ QMA $, existe el inconveniente de que un protocolo QCMA puede comportarse de forma arbitraria en certificados incorrectos a instancias yes. Para ver lo que quiero decir, comience con [1].
Tampoco hay un análogo obvio de un colapso de Karp-Lipton o límites inferiores del circuito de tipo Kannan. Recuerde que en el caso clásico, tenemos
Teorema [3] Por cada $ k \ in \ mathbb {N} $, hay un lenguaje en $ \ Sigma_4 ^ {P} $ que requiere circuitos de tamaño $ \ Omega (n ^ k) $.
La razón por la que no hay (todavía) un teorema que reemplace cada $ P $ en este teorema con $ BQP $ es que un ingrediente crítico en su demostración es que es capaz de adivinar (no determinísticamente) un circuito y luego evaluar ese circuito, es decir, calcular la salida del circuito en una entrada. Claro, podemos adivinar una (descripción de un) circuito cuántico, pero solo podemos decir que lo evaluamos si es un circuito de error acotado, y verificar esto es un problema de $ \ # P $ -Hard.
Scott Aaronson y Andy Drucker prueban algo parecido a un "PH cuántico", yendo solo al segundo nivel:
Teorema [2] Si $ NP \ subset BQP _ {/ qpoly} $ entonces $ \ Pi_2 ^ P \ subseteq QMA ^ {PromiseQMA} $.
Cuando le pregunté a Scott Aaronson, dijo que la gente había estado pensando en esta jerarquía durante más de 15 años, pero nadie la había publicado porque nadie había probado nada que no fuera trivial al respecto. Espero que tú o yo cambiemos eso.
¡Teorema de bonificación! Si $ QMA = coQMA $ entonces $ PH \ subseteq QMA $. Solo para ti, porque llegaste hasta el final de una respuesta larga.
[1] Aharonov, Dorit y col. "La búsqueda de la unicidad: extensión del teorema de Valiant-Vazirani a los escenarios probabilísticos y cuánticos". preimpresión de arXiv arXiv: 0810.4840 (2008).
[2] Aaronson, Scott y Andrew Drucker. "Una caracterización completa del asesoramiento cuántico". Actas del cuadragésimo segundo simposio ACM sobre teoría de la computación. ACM, 2010.
[3] Kannan, Ravi. "Límites inferiores del tamaño del circuito y no reducibilidad a conjuntos dispersos". Información y control 55.1-3 (1982): 40-56.
[4] Vyalyi, Mikhail N. "Qma = pp implica que pp contiene ph". En ECCCTR: Coloquio Electrónico sobre Complejidad Computacional, informes técnicos. 2003.