# Quantum analogues of SPACE complexity classes

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).

• whoops, seems like a quantum analogue of PSPACE is already defined: BQPSPACE and it is equal to PSPACE. – Artem Kaznatcheev Jan 21 '11 at 3:26
• You might want to check "Space-bounded quantum complexity", by John Watrous (cs.uwaterloo.ca/~watrous/Papers/…) – Abel Molina Jan 21 '11 at 3:32
• @Abel this could be an answer. – Suresh Venkat Jan 21 '11 at 9:25
• 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)$. – Robin Kothari Jan 21 '11 at 12:08
• @Suresh Sure, I added the link as an answer, and included part of the information in the abstract as well. – Abel Molina 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)})$

• Do you mean $\Omega(\log n)$? Also, what is $NC^2(2^s)$? – Robin Kothari Jan 21 '11 at 13:40
• @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. – Alessandro Cosentino Jan 21 '11 at 16:42
• @Robin Yes, I mean that, changed it in my answer. I believe that Alessandro's definition for $NC^2(2^s)$ is correct. – Abel Molina 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)

and

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.