Properties of quantum languages
type: Item
instance of: scholarly article
title: Properties of quantum languages
zbMATH Open document ID: 1042.81007
DOI: 10.1023/A:1015226708860
author: R. Smith
published in: International Journal of Theoretical Physics
publication date: 2002-08-20T00:00:00Z
review text: 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.
reviewed by: Ladislav Andrey
Mathematics Subject Classification ID: 81P68
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 1784350
MaRDI profile type: Publication
full work available at URL: a:1015226708860
OpenAlex ID: W163843642
description: scientific article; zbMATH DE number 1784350