Succinctness of two-way probabilistic and quantum finite automata
Abuzer Yakaryılmaz, Cem Say
Abstract
We introduce a new model of two-way finite automaton, which is endowed
with the capability of resetting the position of the tape head to
the left end of the tape in a single move during the
computation. Several variants of this model are examined, with the
following results: The weakest known model of computation where
quantum computers recognize more languages with bounded error than
their classical counterparts is identified. We prove that two-way
probabilistic and quantum finite automata (2PFAs and 2QFAs) can be
considerably more concise than both their one-way versions (1PFAs
and 1QFAs), and two-way nondeterministic finite automata
(2NFAs). For this purpose, we demonstrate several infinite families
of regular languages which can be recognized with some fixed
probability greater than 1 / 2 by just
tuning the transition amplitudes of a 2QFA (and, in one case, a
2PFA) with a constant number of states, whereas the sizes of the
corresponding 1PFAs, 1QFAs and 2NFAs grow without bound. We also
show that 2QFAs with mixed states can support highly efficient
probability amplification.
Full Text: PDF PostScript