# Tag Info

It seems this problem is open. Watrous [J. Comp. Sys. Sci. 59, (pp. 281-326), 1999] proved that any space $s$ bounded quantum Turing Machine (for space constructible $s(n)>\Omega(\log n)$) can be simulated by deterministic Turing machine with $O(s^2)$ space. With the assumption $\mathsf{P \neq SC}$ (where $\mathsf{SC \subseteq P}$ is defined as ...