¿Existe un equivalente cuántico del teorema de la jerarquía del tiempo?

Mi teorema favorito en teoría de la complejidad es el teorema de la jerarquía del tiempo. Sin embargo, esto se hizo en 1965.

Quería saber si había algo similar para Quantum Computing.

Además, si no, ¿cuáles son las personas / grupos que trabajan en esta dirección?

Una cita más reciente para los teoremas de la jerarquía de tiempo es "Una jerarquía de tiempo genérica para modelos semánticos con un consejo" de Dieter van Melkebeek y Konstantin Pervyshev que puede obtener de la página web de Dieter. Las técnicas allí dan una jerarquía de tiempo con 1 bit de asesoramiento para "cualquier modelo semántico razonable" de computación, incluidos los algoritmos cuánticos.

Además, normalmente es relativamente fácil obtener una jerarquía para los problemas prometedores calculados por los modelos semánticos. Un problema de promesa solo requiere un algoritmo para "comportarse bien" (por ejemplo, tener un error acotado) en algunas entradas, aquellas que se eligen para ser parte del problema de promesa. Para las entradas no elegidas como parte de la promesa, el algoritmo puede comportarse de manera arbitraria (por ejemplo, no tener un error acotado). Una jerarquía para problemas de promesa es un resultado del folklore; Dieter van Melkebeek y Jeff Kinne (yo mismo) ofrecen una prueba de la configuración de BPP en "Resultados de la jerarquía espacial para modelos aleatorios y otros modelos semánticos" que puede obtener de Dieter o de mi página web. Esto debería aplicarse también a los algoritmos cuánticos.

Entonces, la respuesta es que los teoremas de jerarquía decente son conocidos por los algoritmos cuánticos que reciben 1 bit de consejo o pueden ignorar entradas problemáticas. Algunas de las técnicas para estos resultados se basan en las propiedades de los algoritmos aleatorios. Sería interesante tratar de explotar las propiedades de los algoritmos cuánticos en el área de los teoremas de jerarquía.

Un área algo relacionada donde hay resultados específicos para los algoritmos cuánticos es el área de los límites inferiores del espacio de tiempo. Hay una encuesta realizada por Dieter van Melkebeek: "Una encuesta de límites más bajos para la satisfacción y los problemas relacionados".

La respuesta es no. Ni siquiera tenemos un teorema de jerarquía de tiempo para tiempo polinómico probabilístico de error acotado (es decir, BPTIME). Los teoremas de la jerarquía temporal determinista y no determinista tienen un argumento de diagonalización, que no parece funcionar para las clases semánticas. Es por eso que no tenemos fuertes teoremas de jerarquía para las clases semánticas.

El mejor resultado que conozco es un teorema de jerarquía para BPTIME con 1 bit de consejo: Fortnow, L .; Santhanam, R. (2004). Teoremas de jerarquía para el tiempo polinomial probabilístico .

No conozco ningún grupo que trabaje en un teorema de jerarquía de tiempo cuántico. Supongo que esto se debe a que parece que el problema de la jerarquía BPTIME es más fácil, por lo que los investigadores atacarían ese problema.

(Preguntas algo relacionadas: ¿Existe una caracterización sintáctica para BPP, BQP o QMA? En MathOverflow y Clases de complejidad semántica vs. sintáctica en teoría).

Las clases no deterministas limitadas por el tiempo y el espacio cuántico son aquellas en las que los lenguajes son los conjuntos de cadenas aceptadas por las máquinas cuánticas de Turing que operan dentro de los límites correspondientes con probabilidad distinta de cero.

En la Sección 8 de " probar el poder de la postselección ", mostramos que existen jerarquías estrictas para las clases cuánticas no deterministas limitadas por el tiempo y el espacio.