¿Hay representaciones descriptivas de la complejidad de las clases de complejidad cuántica?

El título más o menos lo dice todo, pero creo que podría agregar un poco de antecedentes y algunos ejemplos específicos que me interesan.

Los teóricos de la complejidad descriptiva, como Immerman y Fagin, han caracterizado muchas de las clases de complejidad más conocidas utilizando la lógica. Por ejemplo, NP puede caracterizarse con consultas existenciales de segundo orden; P puede caracterizarse con consultas de primer orden con un operador de punto menos fijo agregado.

Mi pregunta es: ¿Ha habido algún intento, especialmente exitoso, de encontrar tales representaciones para las clases de complejidad cuántica, como BQP o NQP? ¿Si no, porque no?

Gracias.

Actualización (moderador) : esta pregunta está completamente respondida por esta publicación en mathoverflow .

Creo que la respuesta de Robins a mi pregunta sobre MO también responde a esta.

Una complejidad descriptiva caracterización de una clase de complejidad da un lenguaje cuya consultas (es decir fórmulas) son exactamente las funciones computables en C . La sintaxis del lenguaje generalmente es muy simple, es decir, dada una cadena q es fácil verificar si q es una consulta bien formada del lenguaje, al menos se espera que sea decidible (pero generalmente la verificación de sintaxis puede realizarse en un clase de pequeña complejidad). Esto implicaría enumerablity eficaz de los problemas en la clase C y daría una caracterización sintáctica para C . (Si la complejidad de la verificación de sintaxis es baja, también podría implicar la existencia de un problema completo para la clase).$C$$C$$q$$q$$C$$C$

En los comentarios anteriores, Robin vinculada a Kord Eickmeyer y papel de Martin Grohe " Aleatorización y Derandomization Ficha Teoría de la Complejidad ", que da una caracterización "complejidad descriptiva" de . Los propios autores señalan en la introducción que esto es diferente de lo que generalmente se entiende por caracterización de complejidad descriptiva:$BPP$

Probamos que , la versión probabilística de la lógica de punto fijo con conteo, captura la clase de complejidad B P P , incluso en estructuras desordenadas. Para estructuras ordenadas, este resultado es una consecuencia directa del Teorema de Immerman-Vardi [7, 8], y para estructuras arbitrarias se deduce de la observación de que podemos definir un orden aleatorio con alta probabilidad en BPIFP + C. Aún así, el resultado es sorprendente a primera vista, debido a su similitud con la pregunta abierta de si hay una lógica captura de P , y porque se cree que P = B P P .$BPIFP+C$$BPP$$P$$P = BPP$ La advertencia es que la lógica no tiene una sintaxis eficaz y por lo tanto no es una “lógica” de acuerdo con [9] definición de Gurevich subyacente a la pregunta para una lógica que capturas P . $BPIFP+C$$P$Sin embargo, creemos que da una descripción completamente adecuada de la clase de complejidad B P P , porque la definición de B P P también es inherentemente ineficaz (en oposición a la definición de P en términos de lo decidible conjunto de máquinas de Turing con reloj polinómico).$BPIFP+C$$BPP$$BPP$$P$

No soy un experto en teoría de modelos finitos / complejidad descriptiva (y personalmente me gustaría saber más de los expertos), pero creo que aquí hay un poco de trampa al decir que esta es una caracterización de complejidad descriptiva. La razón de mi opinión es que si se nos permite tener una sintaxis no efectiva, podemos usar restricciones semánticas arbitrarias para restringir la clase de consultas bien formadas y podemos dar una caracterización de "complejidad descriptiva" para cualquier clase de complejidad. Por ejemplo, considere (que captura P S p a c e ), y luego tome exactamente esas consultas que son computables en B Q $SO(TC)$$PSpace$$BQP$; o considerar el idioma que tiene un símbolo de la función para cada máquina en . Ambos capturan B Q P pero no tienen una sintaxis efectiva.$BQP$$BQP$

Gurevich al formular la conjetura sobre una lógica que podría capturar $\mathsf{P}$$\sigma$$\sigma$$\sigma$$M$$\varphi$$M$$\varphi$$\sigma$$R_1,R_2,\ldots$

$\sigma$$\sigma$$\rho$$\sigma$$\rho$. Esta es mi carnicería de la Definición 1 en el artículo de Eickmeyer-Grohe vinculado por Robin Kothari. En particular, el vocabulario no es finito (bueno, cada vocabulario lo es, pero tenemos que considerar infinitos vocabularios distintos), el conjunto de oraciones de esta lógica es indecidible y la noción de satisfacción es diferente de la presentada por Gurevich .