×

Automata theory based on quantum logic. I. (English) Zbl 0962.03029

The notion of a finite automaton, with finitely many states and a deterministic transition, is one of the basic notions in the theory of computing. It is well known which languages are recognizable by a finite automaton, i.e., for which language \(L\), there exists a finite automaton which, for every input word \(w\), ends up in a special “yes” state if and only if \(w\in L\).
In quantum computing, there is a natural quantum analogue of the notion of a finite automaton. However, when researchers studying quantum computing analyze recognizability by quantum finite automata, they interpret “there exists” and “for every” in the above definition in the sense of the standard (classical) logic. Since we are talking about quantum phenomena, it seems more natural to interpret “there exists” (i.e., disjunction) as a quantum disjunction \(\vee\), and “for all” as a quantum conjunction \(\wedge\). The author uses the known fact – that \(a\vee b\) can true in quantum mechanics without \(a\) or \(b\) being absolutely true – to prove that the new definition is indeed different from the traditionally used one: there exists a (quantum) language which is recognizable in the new sense but not in the traditional one.

MSC:

03D05 Automata and formal grammars in connection with logical questions
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03G12 Quantum logic
PDFBibTeX XMLCite
Full Text: DOI