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

Journal of Sichuan Normal University

Some Properties of Quantum Languages

Guo Xiu-hong

Published Jan 1, 2005• 0 citations
OpenAlex

Abstract

Tensor product of two automata over the different alphabets is defined in this paper and quantum languages accepted by the tensor product are studied. Quantum languages and generalized quantum languages are discussed. Some of their properties are derived.

Related papers

Closure of q-Quantum Languages

Zhiwen Mo

η-quantum languages are discussed and some of their properties are derived. Furthermore the q-quantum language is defined. It is shown that L(A1A2)=L(A1)∩L(A2), L(A)=L(A1)∪L(A2). So over the same alphabet the intersection and union of two different q-quantum languages are also q-quantum languages.

东华大学学报：英文版•Jan 1, 2007•0 citations

Closure of q-Quantum Languages

莫智文, 郭秀红, 舒兰

η-quantum languages are discussed and some of their properties are derived. Furthermore the q-quantum language is defined. It is shown that L(A1A2)=L(A1)∩L(A2), L(A)=L(A1)∪L(A2). So over the same alphabet the intersection and union of two different q-quantum languages are also q-quantum languages.

东华大学学报：英文版•Jan 1, 2007•0 citations

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

Weak Commutativity of Quantum Automata

Feidan Huang, Fasheng Cao

Weak commutativity of quantum automata and weak commutativity of generalized quantum automata are defined. Weak commutativity of (generalized) quantum automata is discussed, and weak commutativity of general direct product, full direct product, restricted direct product, cascade product and wreath product of (generalized) quantum automata are studied, and several necessary and sufficient conditions of weak commutativity of some products of (generalized) quantum automata are obtained.

International Conference on Advances in Computer Technology, Information Science and Communications (CTISC)•Apr 1, 2021•1 citation

Models and characterizations of 1-way quantum finite automata

Brodsky, Alexander

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.

•Jan 1, 2009•1 citation

Quantum Automata and Quantum Grammars

Cristopher Moore, James P. Crutchfield

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.

arXiv:quant-ph/9707031•Jul 16, 1997•4 citations
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.
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.