A theory of computation based on quantum logic

Publication Type:
Conference Proceeding
2005 IEEE International Conference On Granular Computing, 2005, pp. 91 - 91
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2008004723OK.pdf1.47 MB
Adobe PDF
Summary form only given. 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. It is currently understood as a logic whose truth values are taken from an orthomodular lattice. 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. We introduce the notion of orthomodular lattice-valued (quantum) automaton. The Kleene theorem about equivalence of regular expressions and finite automata is generalized into quantum logic. We also present a pumping lemma for orthomodular lattice-valued regular languages.
Please use this identifier to cite or link to this item: