  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.
