Automata theory based on quantum logic. I (Q1586380): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claims
Property / author
 
Property / author: Ming Sheng Ying / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Q497546 / rank
Normal rank
 

Revision as of 10:38, 10 February 2024

scientific article
Language Label Description Also known as
English
Automata theory based on quantum logic. I
scientific article

    Statements

    Automata theory based on quantum logic. I (English)
    0 references
    25 February 2001
    0 references
    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.
    0 references
    quantum logic
    0 references
    finite automata
    0 references
    language recognition
    0 references
    quantum computing
    0 references

    Identifiers