  Quantum computing is a new model of computation, based on quantum physics.
Quantum computers can be exponentially faster than conventional computers for
problems such as factoring. Besides full-scale quantum computers, more
restricted models such as quantum versions of finite automata have been
studied. In this paper, we survey various models of quantum finite automata and
their properties. We also provide some open questions and new directions for
researchers.
  Keywords: quantum finite automata, probabilistic finite automata,
nondeterminism, bounded error, unbounded error, state complexity, decidability
and undecidability, computational complexity
