We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in complexity theory there was much success with these classes such as the space-hierarchy theorem and the creating on important classes like $\textbf{L}$ and $\textbf{PSPACE}$. Is there analogous definitions for quantum computation? Or is there some obvious reason why the quantum analogous would not be interesting?

It seems like it would be important to have a class like $\textbf{QL}$ --- a quantum version of $\textbf{L}$: require a logarithmic number of qubits (or maybe a quantum TM uses logarithmic space).

  • $\begingroup$ whoops, seems like a quantum analogue of PSPACE is already defined: BQPSPACE and it is equal to PSPACE. $\endgroup$ Commented Jan 21, 2011 at 3:26
  • 9
    $\begingroup$ You might want to check "Space-bounded quantum complexity", by John Watrous (cs.uwaterloo.ca/~watrous/Papers/…) $\endgroup$ Commented Jan 21, 2011 at 3:32
  • 1
    $\begingroup$ @Abel this could be an answer. $\endgroup$ Commented Jan 21, 2011 at 9:25
  • 2
    $\begingroup$ For space classes above polynomial space, the quantum and classical classes are equal. As for quantum log space, I can't say much. I would guess that all we can say is $L \subseteq BQL \subseteq DSPACE(\log^2 n)$. $\endgroup$ Commented Jan 21, 2011 at 12:08
  • $\begingroup$ @Suresh Sure, I added the link as an answer, and included part of the information in the abstract as well. $\endgroup$ Commented Jan 21, 2011 at 12:54

2 Answers 2


You might want to check Space-Bounded Quantum Complexity, by John Watrous.

There you have the result that for any $s=\Omega(\log n)$, a Quantum Turing Machine running in space $s$ can be simulated by a probabilistic Turing Machine with unbounded error running in space $O(s)$. You also have that any Quantum Turing Machine running in space $s$ can be simulated in $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$

  • 1
    $\begingroup$ Do you mean $\Omega(\log n)$? Also, what is $NC^2(2^s)$? $\endgroup$ Commented Jan 21, 2011 at 13:40
  • $\begingroup$ @Robin: $NC^2(2^s)$ is the class of problems solvable by a $s$-space uniform family of Boolean circuits, with size $2^{O(s)}$, depth $O(s^2)$, and bounded fan-in. $\endgroup$ Commented Jan 21, 2011 at 16:42
  • $\begingroup$ @Robin Yes, I mean that, changed it in my answer. I believe that Alessandro's definition for $NC^2(2^s)$ is correct. $\endgroup$ Commented Jan 21, 2011 at 16:51

For sublogarithmic space bounds, quantum has been proven to be more powerful than classical, see

Abuzer Yakaryılmaz, A. C. Cem Say, “Unbounded-error quantum computation with small space bounds,” Information and Computation, Vol. 209, pp.873-892, 2011. (slightly older version at arXiv:1007.3624)


Abuzer Yakaryılmaz, A. C. Cem Say, “Languages recognized by nondeterministic quantum finite automata,” Quantum Information and Computation, Vol. 10, pp. 747-770, 2010. (arXiv:0902.2081)

for the unbounded error case. The paper

A. Ambainis and J. Watrous. Two-way finite automata with quantum and classical states. Theoretical Computer Science, 287(1): 299–311, 2002, (arXiv:cs/9911009v1)

together with the fact that the palindrome language cannot be recognized by probabilistic Turing machines with sublogarithmic space, show that the same is also true for the bounded error case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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