Properties of quantum languages (Q1610690): Difference between revisions

Classical automata and regular languages are well described and their properties are well known. With a big progress of quantum computing also a question of quantum automata and quantum languages arise now. In the paper a brief review of classical automata and regular languages with a reformulated definition of the concept of deterministic and stochastic automaton is presented at the beginning. Then the class of reversible languages is introduced. The main part deals with the quantum automaton. The languages that such q-automata accept are called quantum languages. It is shown that a class of quantum languages contains a set of reversible languages and that of finite languages. Then it is demonstrated that quantum languages are closed under union, intersection and reversal but are not closed under complementation, concatenation, or Kleene star. Moreover, it is shown that regular and quantum languages are incomparable, i.e., neither is contained in the other. Finally, a property called transition amplitude function for a given language is defined which is equivalent for a given language to be in the class of quantum languages. A comparison to regular languages of classical automata is made. When one realizes that a quantum automaton is in fact simple type of quantum computer, it is clear, the study of such machines is important. The paper is written in self-consistent way and may be used as introductory guide to the problematics of quantum languages. On the other hand it would be nice to have a possible connection of quantum automata and languages treated here to quantum cellular automata and quantum complexity theory.