15
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ whoops, seems like a quantum analogue of PSPACE is already defined: BQPSPACE and it is equal to PSPACE. $\endgroup$
    – Artem Kaznatcheev ♦
    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$
    – Abel Molina
    Commented Jan 21, 2011 at 3:32
  • 1
    $\begingroup$ @Abel this could be an answer. $\endgroup$
    – Suresh Venkat
    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$
    – Robin Kothari
    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$
    – Abel Molina
    Commented Jan 21, 2011 at 12:54

2 Answers 2

Reset to default
16
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Do you mean $\Omega(\log n)$? Also, what is $NC^2(2^s)$? $\endgroup$
    – Robin Kothari
    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$
    – Alessandro Cosentino
    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$
    – Abel Molina
    Commented Jan 21, 2011 at 16:51
13
$\begingroup$

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.

Improve this answer
$\endgroup$

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.