Standardowy dowód, że BQPSPACE jest w PSPACE, opiera się na analizie typu gry Savitcha na całkach ścieżek. Zakłada się jednak, że długość czasu BQPSPACE jest co najwyżej wykładniczo długa. Dotyczy to PSPACE, ale dla zamkniętych układów kwantowych o ustalonej liczbie stopni swobody zwykle trwa podwójnie wykładniczo długo przed nawrotem Poincare z powodu wykładniczej natury wektora stanu. Czy więc dowód wciąż się sprawdza, czy nie?
Odpowiedzi:
BQPSPACE może wykorzystywać wielomianowe qbity, ale jego obliczenia są sterowane przez klasyczną maszynę. Ta klasyczna maszyna otrzymuje również wielomianową liczbę bitów. Zatem klasyczny komputer ogranicza liczbę kroków do po prostu wykładniczego, niezależnie od tego, co robi komputer kwantowy.
Ograniczenie obwodów długości wykładniczej przez algorytmy wielomianowe wynika z tego, że komputer tworzy obwód w nieskończonej pętli, a nie o stanie lub szczegółach samego obwodu. Obwody kwantowe nie różnią się.