Exploring Quantum Automata and Grammars

Cristopher Moore, James P. Crutchfield

Zhengjun Xi, Yongming Li, Xin Wang

Qiu Dao

The relationships among various quantum automata are clarified, and in particular, variously equivalent characterizations of quantum automata are established. The G-quantum automata, g-quantum automata, (generalized) quantum automata, G-quantum grammars and g-quantum grammars are presented, and their connections to some of the other existing quantum automata are expounded. Under a certain condition, the equivalence between the G(g)-quantum automata and G(g)-quantum grammars is discussed. Therefore the problem of quantum grammars generating quantum regular languages is solved. The relation between quantum and regular languages is dealt with, and particularly, two open problems proposed by Gudder are answered. Finally, the method of decreasing the dimensions of spaces of states on quantum automata is given.

Stanley Gudder

Peng Jia

To increase depictive ability of quantum grammars and overcome difficulties in context sensitive grammars, we put forward the concepts of attributed G (g ) quantum grammars and attributed quantum automata in this paper. The relationship between them is investigated. It is proved that for a given attributed G (g ) quantum grammar G, an attributed quantum automaton Q can be produced such that f Q=f G,X , and vice versa. So attributed G (g ) quantum language can be recognized automatically.

Wei Cheng, Jue Wang

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.