Pourquoi BQPSPACE est-il dans PSPACE s'il peut avoir des durées d'exécution doublement exponentielles?

La preuve standard que BQPSPACE est dans PSPACE repose sur une analyse de type de jeu Savitch sur les intégrales de chemin. Cependant, il suppose que la durée d'exécution de BQPSPACE est au maximum exponentiellement longue. Cela est vrai pour PSPACE, mais pour les systèmes quantiques fermés avec un nombre fixe de degrés de liberté, cela prend généralement un temps doublement exponentiel avant la récurrence de Poincaré en raison de la nature exponentielle du vecteur d'état. Alors, la preuve est-elle toujours valable ou non?

BQPSPACE ne peut utiliser que des qbits polynomiaux, mais son calcul est piloté par une machine classique. Cette machine classique n'obtient également qu'un nombre polynomial de bits. Ainsi, l'ordinateur classique limite le nombre d'étapes à simplement exponentiel, indépendamment de ce que fait l'ordinateur quantique.

La limitation des circuits de longueur exponentielle par les algorithmes de taille polynomiale est due au fait que l'ordinateur crée le circuit dans une boucle infinie, pas à propos de l'état ou des détails du circuit lui-même. Les circuits quantiques ne sont pas différents.