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$ Jan 21 '11 at 3:26
  • 9
    $\begingroup$ You might want to check "Space-bounded quantum complexity", by John Watrous (cs.uwaterloo.ca/~watrous/Papers/…) $\endgroup$ Jan 21 '11 at 3:32
  • 1
    $\begingroup$ @Abel this could be an answer. $\endgroup$ Jan 21 '11 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$ Jan 21 '11 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$ Jan 21 '11 at 12:54

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$ Jan 21 '11 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$ Jan 21 '11 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$ Jan 21 '11 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, privacy policy and cookie policy

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