State Key Laboratory of Intelligent Technology and Systems

Title: State Key Laboratory of Intelligent Technology and Systems

Research Question: How can quantum logic be applied to the theory of computation, and what are the implications for our understanding of automata and regular languages?

Methodology: The authors propose a theory of computation based on quantum logic, focusing on the concept of orthomodular lattice-valued (quantum) automata. They reexamine various properties of automata within the framework of quantum logic, using an approach of semantic analysis.

Results: The authors introduce the notion of orthomodular lattice-valued automaton and study its acceptance abilities. They compare the abilities of orthomodular lattice-valued nondeterministic automata and deterministic automata, as well as automata with ε-moves. They derive closure properties of orthomodular lattice-valued regular languages and generalize the Kleene theorem into quantum logic. They also present a pumping lemma for orthomodular lattice-valued regular languages.

Implications: The authors find that many properties of automata, such as the Kleene theorem and the equivalence of deterministic and nondeterministic automata, do not universally hold in the realm of quantum logic. However, they show that a local validity of these properties 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.

Link to Article: https://arxiv.org/abs/0403041v1 Authors: arXiv ID: 0403041v1