  The (meta)logic underlying classical theory of computation is Boolean
(two-valued) logic. Quantum logic was proposed by Birkhoff and von Neumann as a
logic of quantum mechanics more than sixty years ago. The major difference
between Boolean logic and quantum logic is that the latter does not enjoy
distributivity in general. The rapid development of quantum computation in
recent years stimulates us to establish a theory of computation based on
quantum logic. The present paper is the first step toward such a new theory and
it focuses on the simplest models of computation, namely finite automata. It is
found that the universal validity of many properties of automata depend heavily
upon the distributivity of the underlying logic. This indicates that these
properties does not universally hold in the realm of quantum logic. On the
other hand, we show that a local validity of them can be recovered by imposing
a certain commutativity to the (atomic) statements about the automata under
consideration. This reveals an essential difference between the classical
theory of computation and the computation theory based on quantum logic.
