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:2505.13937

On Quantum Context-Free Grammars

Merina Aruja, Lisa Mathew, Jayakrishna Vijayakumar

Published May 20, 2025• 1 citation
arXivHTMLPDF

Abstract

Quantum computing is a relatively new field of computing, which utilises the fundamental concepts of quantum mechanics to process data. The seminal paper of Moore et al. [2000] introduced quantum grammars wherein a set of amplitudes was attached to each production. However they did not study the final probability of the derived word. Aruja et al. [2025] considered conditions for the well-formedness of quantum context-free grammars (QCFGs), in order to ensure that the probabilty of the derived word does not exceed one. In this paper we propose certain necessary and sufficient conditions (also known as unitary conditions) for well-formedness of QCFGs

DOI
10.48550/arxiv.2505.13937

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

An Algebraic Approach to the Study of Quantum Finite Automata

Andrea Benso

In this thesis we will study the decidability of the Intersection problem for the measure-once quantum finite automata introduced by Moore and Crutchfield in the 2000s. Specifically, we ask for which families of grammars it is possible to find conditions ensuring that, given a language recognized by such model of computation and a language generated by such families of grammars, it is decidable whether or not they have a nonempty intersection. Throughout the thesis, we will investigate the correlation between this problem and some decidability problems for matrices subsets on the Zariski topology, so as to apply the corresponding results to show the decidability of the problem for languages generated by monoidal context-free grammars and restricted matrix context-free grammars of finite index.

•Jan 1, 2025•0 citations

The physical structure of grammatical correlations: equivalences, formalizations and consequences.

Ángel J. Gallego, Román Orús

Here we consider some well-known facts in syntax from a physics perspective, allowing us to establish equivalences between both fields with many consequences. Mainly, we observe that the operation MERGE, put forward by N. Chomsky in 1995, can be interpreted as a physical information coarse-graining. Thus, MERGE in linguistics entails information renormalization in physics, according to different time scales. We make this point mathematically formal in terms of language models. In this setting, MERGE amounts to a probability tensor implementing a coarse-graining, akin to a probabilistic context-free grammar. The probability vectors of meaningful sentences are given by stochastic tensor networks (TN) built from diagonal tensors and which are mostly loop-free, such as Tree Tensor Networks and Matrix Product States, thus being computationally very efficient to manipulate. We show that this implies the polynomially-decaying (long-range) correlations experimentally observed in language, and also provides arguments in favour of certain types of neural networks for language processing. Moreover, we show how to obtain such language models from quantum states that can be efficiently prepared on a quantum computer, and use this to find bounds on the perplexity of the probability distribution of words in a sentence. Implications of our results are discussed across several ambits.

arXiv:1708.01525•Aug 4, 2017•4 citations

Epistemic Quantum Computational Structures in a Hilbert-space Environment

Enrico G. Beltrametti, María Luisa Dalla Chiara, Roberto Giuntini +2 more

Quantum computation and quantum computational logics are intrinsically connected with some puzzling epistemic problems. In the framework of a quantum computational approach to epistemic logic we investigate the following question: is it possible to i

Fundamenta Informaticae•Jan 1, 2012•17 citations

Weakly Regular Quantum Grammars and Asynchronous Quantum Automata

Zhengjun Xi, Yongming Li, Xin Wang

International Journal of Theoretical Physics•Jul 25, 2008•0 citations

Quantum automata and quantum grammars

Cristopher Moore, James P. Crutchfield

arXiv:quant-ph/9707031•Theoretical Computer Science•Apr 1, 2000•425 citations
Quantum computing is a relatively new field of computing, which utilises the fundamental concepts of quantum mechanics to process data. The seminal paper of Moore et al. [2000] introduced quantum grammars wherein a set of amplitudes was attached to each production. However they did not study the final probability of the derived word. Aruja et al. [2025] considered conditions for the well-formedness of quantum context-free grammars (QCFGs), in order to ensure that the probabilty of the derived word does not exceed one. In this paper we propose certain necessary and sufficient conditions (also known as unitary conditions) for well-formedness of QCFGs
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.
In this thesis we will study the decidability of the Intersection problem for the measure-once quantum finite automata introduced by Moore and Crutchfield in the 2000s. Specifically, we ask for which families of grammars it is possible to find conditions ensuring that, given a language recognized by such model of computation and a language generated by such families of grammars, it is decidable whether or not they have a nonempty intersection. Throughout the thesis, we will investigate the correlation between this problem and some decidability problems for matrices subsets on the Zariski topology, so as to apply the corresponding results to show the decidability of the problem for languages generated by monoidal context-free grammars and restricted matrix context-free grammars of finite index.
Here we consider some well-known facts in syntax from a physics perspective, allowing us to establish equivalences between both fields with many consequences. Mainly, we observe that the operation MERGE, put forward by N. Chomsky in 1995, can be interpreted as a physical information coarse-graining. Thus, MERGE in linguistics entails information renormalization in physics, according to different time scales. We make this point mathematically formal in terms of language models. In this setting, MERGE amounts to a probability tensor implementing a coarse-graining, akin to a probabilistic context-free grammar. The probability vectors of meaningful sentences are given by stochastic tensor networks (TN) built from diagonal tensors and which are mostly loop-free, such as Tree Tensor Networks and Matrix Product States, thus being computationally very efficient to manipulate. We show that this implies the polynomially-decaying (long-range) correlations experimentally observed in language, and also provides arguments in favour of certain types of neural networks for language processing. Moreover, we show how to obtain such language models from quantum states that can be efficiently prepared on a quantum computer, and use this to find bounds on the perplexity of the probability distribution of words in a sentence. Implications of our results are discussed across several ambits.