Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9707031

Quantum Automata and Quantum Grammars

Cristopher Moore, James P. Crutchfield

Published Jul 16, 1997• 4 citations
arXivHTMLPDF

Abstract

To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and push-down automata, and regular and context-free grammars. We find analogs of several classical theorems, including pumping lemmas, closure properties, rational and algebraic generating functions, and Greibach normal form. We also show that there are quantum context-free languages that are not context-free.

DOI
10.48550/arxiv.quant-ph/9707031

Related papers

Regular quantum grammars and regular grammars

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.

International Conference on Communications, Circuits and Systems•Jan 1, 2004•1 citation

Characterizations of Quantum Automata

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.

•Jan 1, 2003•0 citations

Quantum automata and quantum computing

Marats Golovkins

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).

•Jan 1, 2002•0 citations

Quantum Representation for Deterministic Push-Down Automata

Varun Puram, K. M. George, Johnson P. Thomas

Abstract There are many papers presenting quantum computing models. The definitions parallel the classical definitions of finite state automata, push down automata, context-free grammars etc. Classical computing model definitions define languages precisely. We can state that a string belongs to a language or does not belong to it with no room for error. Quantum definitions do not possess this certainty. Sacrificing the certainty and adopting a quantum definition of a computing model does not appear to provide any concrete power to the model. Therefore, the path of this paper is to begin from the classical definition and end in a quantum circuit. In this paper we start from a Deterministic Push-Down Automaton (DPDA). We present circuit for state transition and stack operations. The circuits presented can be viewed as independent algorithms. As an example, the approach used to construct the circuit for state transition can be utilized to build the circuit for a function presented as a Boolean matrix.

Electronics•Nov 18, 2024•0 citations

On the power of quantum finite state automata

A. Kondacs, John Watrous

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•348 citations

On the Weakness of One-Way Quantum Pushdown Automata

Masaki Nakanishi

In general, quantum computation models are expected to be more powerful than classical counterparts. However, sometimes this is not the case.It is known that there exists some regular language which one-way quantum finite automata and one-way quantum counter automata cannot recognize. This is due to the restriction of reversibility which quantum models must satisfy. Thus, it is an interesting question: what kinds of quantum models suffer from/overcome the restriction? To tackle this problem, we focus on (empty-stack acceptance) one-way quantum pushdown automata, and show that there exists a regular language which one-way quantum pushdown automata cannot recognize. This implies adding a stack to one-way finite automata cannot overcome the restriction of reversibility if we adopt empty-stack acceptance as the acceptance mode.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2010•0 citations
To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and push-down automata, and regular and context-free grammars. We find analogs of several classical theorems, including pumping lemmas, closure properties, rational and algebraic generating functions, and Greibach normal form. We also show that there are quantum context-free languages that are not context-free.
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.
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.
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).
Abstract There are many papers presenting quantum computing models. The definitions parallel the classical definitions of finite state automata, push down automata, context-free grammars etc. Classical computing model definitions define languages precisely. We can state that a string belongs to a language or does not belong to it with no room for error. Quantum definitions do not possess this certainty. Sacrificing the certainty and adopting a quantum definition of a computing model does not appear to provide any concrete power to the model. Therefore, the path of this paper is to begin from the classical definition and end in a quantum circuit. In this paper we start from a Deterministic Push-Down Automaton (DPDA). We present circuit for state transition and stack operations. The circuits presented can be viewed as independent algorithms. As an example, the approach used to construct the circuit for state transition can be utilized to build the circuit for a function presented as a Boolean matrix.
In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.
In general, quantum computation models are expected to be more powerful than classical counterparts. However, sometimes this is not the case.It is known that there exists some regular language which one-way quantum finite automata and one-way quantum counter automata cannot recognize. This is due to the restriction of reversibility which quantum models must satisfy. Thus, it is an interesting question: what kinds of quantum models suffer from/overcome the restriction? To tackle this problem, we focus on (empty-stack acceptance) one-way quantum pushdown automata, and show that there exists a regular language which one-way quantum pushdown automata cannot recognize. This implies adding a stack to one-way finite automata cannot overcome the restriction of reversibility if we adopt empty-stack acceptance as the acceptance mode.