  We present a language $L_n$ which is recognizable by a probabilistic finite
automaton (PFA) with probability $1 - \epsilon$ for all $\epsilon > 0$ with
$O(log^2n)$ states, with a deterministic finite automaton (DFA) with O(n)
states, but a quantum finite automaton (QFA) needs at least $2^{\Omega(n/ \log
n)}$ states.
