To study quantum computation, Moore and Crutchfield (Theoret. Comput. Sci. vol. 237, pp. 275-306, 2000) proposed quantum versions of finite-state and push-down automata, as well as regular and context-free grammars. In this note, we show that the languages generated by regular quantum grammars are equivalent to the languages generated by regular grammars. Therefore, from the perspective of generating languages, regular quantum grammars are not more powerful than classical regular grammars. This implies that it may be necessary to look for more well-formed definitions of quantum grammars and maybe those of quantum automata.
Quantum finite automata were introduced by C.Moore and J.P.Crutchfield in [MC 97] and by A.Kondacs and J.Watrous in [KW 97]. This notion is not a generalization of the deterministic finite automata, but rather a generalization of deterministic reversible (permutation) automata. In [AF 98] A.Ambainis and R.Freivalds raised the question what kind of probabilistic automata can be viewed as a special case of quantum finite automata. To answer that question and study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We give the necessary condition for a language to be recognized by PRA. We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. In these thesis we regard quantum automata, probabilistic reversible and deterministic reversible automata as reversible automata. At least two non-equivalent definitions of language recognition are used for one-way reversible finite automata in various papers. Both of these definitions have their own advantages and disadvantages, summarized in our classification of one-way reversible automata. Further, we introduce a notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite multitape automaton but not by deterministic finite multitape automata. Additionally we discover unexpected probabilistic automata recognizing complicated languages. Finally, we revise the concept of quantum pushdown automata (QPA), first introduced by C.Moore and J.P.Cruthchfield in [MC 97]. We give the definition of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [KW 97]. It is established that the unitary criteria of QPA are not equivalent to the corresponding unitary criteria of quantum Turing machines [BV 97]. We show that QPA can recognize every regular language. We also present some simple non-context-free languages recognized by QPA (hence not recognizable by deterministic and nondeterministic pushdown automata).
The notion of quantum Bchi automaton(LVBA for short)is introduced,by means of quantum state construction, the equivalence of an LVBA and an LVSBA with crisp transition function is proved,based on this,the algebraic and level characterizations and also the Bchi characterization of quantum infinite regular languages are investigated,and also the closed properties of those quantum infinite regular languages under some regular operations are dealt with.By providing the concept of monadic secondorder quantum logic(LVMSO in short),the monadic second-order logic characterizations of infinite regular languages recognized by quantum Biichi automata are presented,which deepen and generalize the fundamental Bchi theorem to quantum setting.
In the past year two different models of quantum finite automata have been proposed. The first model, introduced by Moore and Crutchfield[MC98], makes one measurement on its state at the end of its computation and is called a measure-once quantum finite automata. The second model, introduced by Kondacs and Watrous[KW97], makes a measurement of its state after every transition and is called a measure-many quantum finite automata. In this thesis we investigate the characteristics of the two models. We characterize measure-once quantum finite automata when they are restricted to acceptance with bounded error, and we show that, when they are not so restricted, they can solve the word problem over the free group. We show that they can be simulated by probabilistic finite automata, which implies that they are no more powerful than probabilistic finite automata. We also describe an algorithm that determines if two automata are equivalent. We show that the class of languages accepted by measure-many quantum finite automata is closed under quotient, complement, and inverse homomorphisms. We prove a necessary condition for a language to be accepted by a measure-many automaton with bounded error and we show that certain sets, including piecewise testable sets, can be accepted with bounded error by this automata.
We first show that given a
k1-letter quantum finite automata
A1 and a
k2-letter quantum finite automata
A2 over the same input alphabet
Σ, they are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
n1,
i=1,2, are the numbers of state in
Ai respectively, and
k=max{k1,k2}. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a
k1-letter measure many quantum finite automaton
A1 and a
k2-letter measure many quantum finite automaton
A2 are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
ni,
i=1,2, are the numbers of state in
Ai respectively, and
k=max{k1,k2}. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for
k-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether
L≥λ(A1)=L≥λ(A2) where
0<λ≤1 and
Ai are
ki-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for
k-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.