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

<p>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 <a href="http://arxiv.org/abs/1007.3624">arXiv:1007.3624</a>)</p>

<p>and</p>

<p>Abuzer Yakaryılmaz, A. C. Cem Say, “Languages recognized by nondeterministic quantum finite automata,” Quantum Information and Computation, Vol. 10, pp. 747-770, 2010. (<a href="http://arxiv.org/abs/0902.2081">arXiv:0902.2081</a>)</p>

<p>for the unbounded error case. The paper</p>

<p>A. Ambainis and J. Watrous. Two-way finite automata with quantum and classical states. Theoretical Computer Science, 287(1): 299–311, 2002, (<a href="http://arxiv.org/abs/cs/9911009">arXiv:cs/9911009v1</a>)</p>

<p>together with the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.7657&amp;rep=rep1&amp;type=pdf">fact</a> 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.</p>

CC BY-SA 2.5
2011-04-01T09:47:05.483Z
2011-04-01T20:51:29.657Z
2011-04-01T20:51:29.657Z
Cem Say
<p>You might want to check <a href="https://cs.uwaterloo.ca/~watrous/Papers/SpaceBoundedQuantumComplexity.pdf" rel="nofollow"> Space-Bounded Quantum Complexity</a>, by John Watrous.</p>

<p>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)})$ </p>

CC BY-SA 2.5
2011-01-21T13:40:00.367Z
Do you mean $\Omega(\log n)$? Also, what is $NC^2(2^s)$?
Robin Kothari
CC BY-SA 2.5
2011-01-21T16:42:00.140Z
@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
CC BY-SA 2.5
2011-01-21T16:51:51.590Z
@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
CC BY-SA 3.0
2011-01-21T12:53:05.417Z
2016-01-13T12:54:56.767Z
2016-01-13T12:54:56.767Z
Abel Molina
<p>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?</p>

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

CC BY-SA 2.5
2011-01-21T03:26:54.923Z
whoops, seems like a quantum analogue of PSPACE is already defined: BQPSPACE and it is equal to PSPACE.
Artem Kaznatcheev
CC BY-SA 2.5
2011-01-21T03:32:07.820Z
You might want to check "Space-bounded quantum complexity", by John Watrous (http://www.cs.uwaterloo.ca/~watrous/Papers/SpaceBoundedQuantumComplexity.pdf)
Abel Molina
CC BY-SA 2.5
2011-01-21T09:25:52.247Z
@Abel this could be an answer.
Suresh Venkat
CC BY-SA 2.5
2011-01-21T12:08:51.053Z
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
CC BY-SA 2.5
2011-01-21T12:54:58.363Z
@Suresh Sure, I added the link as an answer, and included part of the information in the abstract as well.
Abel Molina
<cc.complexity-theory><complexity-classes><quantum-computing><space-bounded>
Quantum analogues of SPACE complexity classes
Artem Kaznatcheev
# Quantum analogues of SPACE complexity classes

(Asked by: username_0 on 2011-01-21)

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

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, space-bounded

> **Comments:**
> **username_0**: whoops, seems like a quantum analogue of PSPACE is already defined: BQPSPACE and it is equal to PSPACE.  
> **username_1**: You might want to check "Space-bounded quantum complexity", by John Watrous (http://www.cs.uwaterloo.ca/~watrous/Papers/SpaceBoundedQuantumComplexity.pdf)  
> **username_2**: @Abel this could be an answer.  
> **username_3**: 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)$.  
> **username_1**: @Suresh Sure, I added the link as an answer, and included part of the information in the abstract as well.  

---

## 2 answers

### Answer by username_1 on 2011-01-21. Score: 16 | Accepted answer

You might want to check  [Space-Bounded Quantum Complexity](https://cs.uwaterloo.ca/~watrous/Papers/SpaceBoundedQuantumComplexity.pdf), 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)})$

> **Comments:**
> **username_3**: Do you mean $\Omega(\log n)$? Also, what is $NC^2(2^s)$?  
> **username_5**: @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.  
> **username_1**: @Robin Yes, I mean that, changed it in my answer. I believe that Alessandro's definition for $NC^2(2^s)$ is correct.  

---

### Answer by username_4 on 2011-04-01. Score: 13

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

Abuzer Yakaryılmaz, A. C. username_4, “Unbounded-error quantum computation with small space bounds,” Information and Computation, Vol. 209, pp.873-892, 2011. (slightly older version at [arXiv:1007.3624](http://arxiv.org/abs/1007.3624))

and

Abuzer Yakaryılmaz, A. C. username_4, “Languages recognized by nondeterministic quantum finite automata,” Quantum Information and Computation, Vol. 10, pp. 747-770, 2010. ([arXiv:0902.2081](http://arxiv.org/abs/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](http://arxiv.org/abs/cs/9911009))

together with the [fact](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.7657&rep=rep1&type=pdf) 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.


---

