Existe um equivalente quântico do teorema da hierarquia de tempo?

Meu teorema favorito na teoria da complexidade é o teorema da hierarquia de tempo. No entanto, isso foi feito em 1965.

Eu queria saber se havia algo semelhante para a computação quântica.

Além disso, se não, quais são as pessoas / grupos trabalhando nessa direção!

Uma citação mais recente para os teoremas da hierarquia de tempo é "Uma hierarquia de tempo genérica para modelos semânticos com um pouco de conselho", de Dieter van Melkebeek e Konstantin Pervyshev, que você pode obter na página de Dieter. As técnicas fornecem uma hierarquia de tempo com 1 bit de conselho para "qualquer modelo semântico razoável de computação", incluindo algoritmos quânticos.

Além disso, normalmente é relativamente fácil obter uma hierarquia para os problemas de promessa calculados por modelos semânticos. Um problema de promessa requer apenas que um algoritmo "se comporte bem" (por exemplo, com erro delimitado) em algumas entradas - aquelas que são escolhidas para fazer parte do problema de promessa. Para entradas não escolhidas para fazer parte da promessa, o algoritmo pode se comportar arbitrariamente (por exemplo, sem erro delimitado). Uma hierarquia para problemas de promessa é um resultado folclórico; uma prova da configuração BPP é fornecida em "Resultados da hierarquia espacial para modelos aleatórios e outros modelos semânticos", de Dieter van Melkebeek e Jeff Kinne (eu) que você pode obter na Dieter ou na minha página da web. Isso também deve se aplicar aos algoritmos quânticos.

Portanto, a resposta é que os teoremas da hierarquia decente são conhecidos por algoritmos quânticos que recebem um pouco de conselho ou podem ignorar entradas problemáticas. Algumas das técnicas para esses resultados dependem das propriedades de algoritmos aleatórios. Seria interessante tentar explorar as propriedades dos algoritmos quânticos na área dos teoremas da hierarquia.

Uma área um pouco relacionada onde existem resultados específicos para algoritmos quânticos é a área dos limites inferiores do tempo-espaço. Há uma pesquisa feita por Dieter van Melkebeek: "Uma pesquisa sobre limites mais baixos de satisfação e problemas relacionados".

A resposta é não. Nem sequer temos um teorema da hierarquia de tempo para o tempo polinomial probabilístico de erro limitado (ou seja, BPTIME). Os teoremas da hierarquia de tempo determinísticos e não determinísticos têm um argumento de diagonalização, que parece não funcionar para classes semânticas. É por isso que não temos fortes teoremas de hierarquia para classes semânticas.

O melhor resultado que eu conheço é um teorema de hierarquia para BPTIME com 1 bit de conselho: Fortnow, L .; Santhanam, R. (2004). Teoremas de hierarquia para tempo polinomial probabilístico .

Não conheço nenhum grupo trabalhando no teorema da hierarquia quântica de tempo. Eu acho que isso ocorre porque parece que o problema da hierarquia BPTIME é mais fácil, então os pesquisadores atacariam esse problema.

(Perguntas um pouco relacionadas: Existe uma caracterização sintática para BPP, BQP ou QMA? Nas classes MathOverflow e Complexidade Semântica vs. Sintática na história.)

As classes quânticas não determinísticas, limitadas pelo tempo e pelo espaço, são aquelas em que as línguas são os conjuntos de strings aceitos pelas máquinas quânticas de Turing que operam dentro dos limites correspondentes com probabilidade diferente de zero.

Na Seção 8 de " provar o poder da pós-seleção ", mostramos que existem hierarquias rígidas para as classes limitadas de tempo e espaço quânticas não determinísticas.