  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 a single qubit, can recognize, with
bounded error, the language $L_{eq}=\{a^m b^m :m \in \mathbb{N}\}$ in expected
polynomial time and the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a
palindrome}\}$ in expected exponential time.
  We further demonstrate the power of 2QCFA by showing that they can recognize
the word problems of many groups. In particular 2QCFA, with a single qubit and
algebraic number transition amplitudes, can recognize, with bounded error, the
word problem of any finitely generated virtually abelian group in expected
polynomial time, as well as the word problems of a large class of linear groups
in expected exponential time. This latter class (properly) includes all groups
with context-free word problem. We also exhibit results for 2QCFA with any
constant number of qubits.
  As a corollary, we obtain a direct improvement on the original Ambainis and
Watrous result by showing that $L_{eq}$ can be recognized by a 2QCFA with
better parameters. As a further corollary, we show that 2QCFA can recognize
certain non-context-free languages in expected polynomial time.
  In a companion paper, we prove matching lower bounds, thereby showing that
the class of languages recognizable with bounded error by a 2QCFA in expected
$\mathit{subexponential}$ time is properly contained in the class of languages
recognizable with bounded error by a 2QCFA in expected $\mathit{exponential}$
time.
