11
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.