Por que o BQPSPACE no PSPACE pode ter tempos de execução duplamente exponencialmente longos?

A prova padrão de que o BQPSPACE está no PSPACE depende de uma análise do tipo de jogo Savitch nas integrais do caminho. No entanto, assume que o tempo de execução do BQPSPACE é no máximo exponencialmente longo. Isso é verdade para o PSPACE, mas para sistemas quânticos fechados com um número fixo de graus de liberdade, normalmente leva um tempo duplamente exponencial até a recorrência do Poincaré devido à natureza exponencial do vetor de estado. Então, a prova ainda é completa ou não?

O BQPSPACE pode usar apenas qbits polinomiais, mas seu cálculo é conduzido por uma máquina clássica. Essa máquina clássica também obtém apenas um número polinomial de bits. Assim, o computador clássico limita o número de etapas a simplesmente exponencial, independentemente do que o computador quântico faça.

A limitação dos circuitos de comprimento exponencial pelos algoritmos de tamanho polinomial se deve ao computador que cria o circuito entrando em um loop infinito, não sobre o estado ou os detalhes do próprio circuito. Os circuitos quânticos não são diferentes.