7

There is evidently a classical polynomial-time algorithm for finding a four-coloring of a given planar graph, so the answer to the question is "yes" for the trivial reason that every polynomial-time classical algorithm can be implemented as a polynomial-time quantum algorithm. (Also, polynomial time implies polynomial space, for both quantum and classical ...


4

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


Only top voted, non community-wiki answers of a minimum length are eligible