<p>BQPSPACE can only use polynomial qbits, but its computation is driven by a classical machine. This classical machine also only gets a polynomial number of bits. Thus, the classical computer limits the number of steps to simply exponential, regardless of what the quantum computer does. </p>

<p>The limitation of exponential length circuits by polynomial size algorithms is due to the computer creating the circuit getting in an infinite loop, not about the state or details of the circuit itself. Quantum circuits are no different.</p>

CC BY-SA 3.0
2017-12-31T01:58:41.267Z
2017-12-31T01:58:41.267Z
Joshua Cook
<p>The standard proof that BQPSPACE is in PSPACE relies on a Savitch game type analysis on path integrals. However, it assumes the time running length for BQPSPACE is at most exponentially long. This is true for PSPACE, but for closed quantum systems with a fixed number of degrees of freedom, it typically takes a doubly exponentially long time before Poincare recurrence due to the exponential nature of the state vector. So, does the proof still run through, or not?</p>

<quantum-computing>
Why is BQPSPACE in PSPACE if it can have doubly exponentially long running times?
Pushka Lutin
# Why is BQPSPACE in PSPACE if it can have doubly exponentially long running times?

(Asked by: username_0 on 2014-06-03)

The standard proof that BQPSPACE is in PSPACE relies on a Savitch game type analysis on path integrals. However, it assumes the time running length for BQPSPACE is at most exponentially long. This is true for PSPACE, but for closed quantum systems with a fixed number of degrees of freedom, it typically takes a doubly exponentially long time before Poincare recurrence due to the exponential nature of the state vector. So, does the proof still run through, or not?

**Tags:** quantum-computing


---

## 1 answers

### Answer by username_1 on 2017-12-31. Score: 3

BQPSPACE can only use polynomial qbits, but its computation is driven by a classical machine. This classical machine also only gets a polynomial number of bits. Thus, the classical computer limits the number of steps to simply exponential, regardless of what the quantum computer does.

The limitation of exponential length circuits by polynomial size algorithms is due to the computer creating the circuit getting in an infinite loop, not about the state or details of the circuit itself. Quantum circuits are no different.


---

