The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}$ with bounded error in expected time $2^{O(n)}$, on inputs of length $n$.

We prove that their result essentially cannot be improved upon: a 2QCFA (of any size) cannot recognize $L_{pal}$ with bounded error in expected time $2^{o(n)}$. To our knowledge, this is the first example of a language that can be recognized with bounded error by a 2QCFA in exponential time but not in subexponential time. Moreover, we prove that a quantum Turing machine (QTM) running in space $o(\log n)$ and expected time $2^{n^{1-\Omega(1)}}$ cannot recognize $L_{pal}$ with bounded error; again, this is the first lower bound of its kind.

Far more generally, we establish a lower bound on the running time of any 2QCFA or $o(\log n)$-space QTM that recognizes any language $L$ in terms of a natural ``hardness measure" of $L$. This allows us to exhibit a large family of languages for which we have asymptotically matching lower and upper bounds on the running time of any such 2QCFA or QTM recognizer.

Updated paper to include new results concerning lower bounds on the running time of sublogarithmic-space quantum Turing machines and further ``dequantumization" results. Title changed accordingly. Removed material concerning lower bounds on one-way quantum finite automata, which will appear as a separate paper.

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}$ with bounded-error in expected exponential time. We prove that their result essentially cannot be improved upon: a 2QCFA (of any finite size) cannot recognize $L_{pal}$ with bounded-error in expected time $2^{o(n)}$, on inputs of length $n$. To our knowledge, this is the first example of a language that can be recognized with bounded-error by a 2QCFA in exponential time but not in subexponential time. A key tool in our result is a generalization to 2QCFA of a technical lemma that was used by Dwork and Stockmeyer to prove a lower bound on the expected running time of any two-way probabilistic finite automaton that recognizes a non-regular language with bounded-error.

Furthermore, we prove strong lower bounds on the expected running time of any 2QCFA that recognizes a group word problem with bounded-error. In a recent paper, we showed that 2QCFA can recognize, with bounded-error, a broad class of group word problems in expected exponential time, and a more narrow class of group word problems in expected polynomial time. As a consequence, we can now exhibit a large family of natural languages that can be recognized with bounded-error by a 2QCFA in expected exponential time, but not in expected subexponential time. Moreover, we obtain significant progress towards a precise classification of those group word problems that can be recognized with bounded-error in expected polynomial time by a 2QCFA.

We also consider the one-way measure-once quantum finite automaton (1QFA), defined by Moore and Crutchfield, as well as a natural generalization to one-way measure-once finite automata with quantum and classical states (1QCFA). We precisely classify those groups whose word problem may be recognized with positive one-sided error (for both the bounded-error and unbounded-error cases) by a 1QFA or 1QCFA with any particular number of quantum states and any particular number of classical states; we also obtain partial results in the negative one-sided error case. As an immediate corollary, we show that allowing a 1QFA or 1QCFA to have even a single additional quantum or classical state enlarges the class of languages that may be recognized with positive one-sided error (of either type).