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:1608.01406 · Electronic Proceedings in Theoretical Computer Science

Quantum Algorithms for Compositional Natural Language Processing

William J. Zeng, Bob Coecke

Published Aug 2, 2016• 77 citations
arXivHTMLPDF

Abstract

We propose a new application of quantum computing to the field of natural language processing. Ongoing work in this field attempts to incorporate grammatical structure into algorithms that compute meaning. In (Coecke, Sadrzadeh and Clark, 2010), the authors introduce such a model (the CSC model) based on tensor product composition. While this algorithm has many advantages, its implementation is hampered by the large classical computational resources that it requires. In this work we show how computational shortcomings of the CSC approach could be resolved using quantum computation (possibly in addition to existing techniques for dimension reduction). We address the value of quantum RAM (Giovannetti,2008) for this model and extend an algorithm from Wiebe, Braun and Lloyd (2012) into a quantum algorithm to categorize sentences in CSC. Our new algorithm demonstrates a quadratic speedup over classical methods under certain conditions.

DOI
10.4204/eptcs.221.8

Related papers

QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer

Robin Lorenz, Anna Pearson, Konstantinos Meichanetzidis +2 more

Quantum Natural Language Processing (QNLP) deals with the design and implementation of NLP models intended to be run on quantum hardware. In this paper, we present results on the first NLP experiments conducted on Noisy Intermediate-Scale Quantum (NISQ) computers for datasets of size greater than 100 sentences. Exploiting the formal similarity of the compositional model of meaning by Coecke, Sadrzadeh, and Clark (2010) with quantum theory, we create representations for sentences that have a natural mapping to quantum circuits. We use these representations to implement and successfully train NLP models that solve simple sentence classification tasks on quantum hardware. We conduct quantum simulations that compare the syntax-sensitive model of Coecke et al. with two baselines that use less or no syntax; specifically, we implement the quantum analogues of a “bag-of-words” model, where syntax is not taken into account at all, and of a word-sequence model, where only word order is respected. We demonstrate that all models converge smoothly both in simulations and when run on quantum hardware, and that the results are the expected ones based on the nature of the tasks and the datasets used. Another important goal of this paper is to describe in a way accessible to AI and NLP researchers the main principles, process and challenges of experiments on quantum hardware. Our aim in doing this is to take the first small steps in this unexplored research territory and pave the way for practical Quantum Natural Language Processing.

arXiv:2102.12846•Journal of Artificial Intelligence Research•Apr 30, 2023•121 citations

A gentle introduction to Quantum Natural Language Processing

Shervin Le Du, Senaida Hernández Santana, Scarpa, Giannicola

The main goal of this master's thesis is to introduce Quantum Natural Language Processing (QNLP) in a way understandable by both the NLP engineer and the quantum computing practitioner. QNLP is a recent application of quantum computing that aims at representing sentences' meaning as vectors encoded into quantum computers. To achieve this, the distributional meaning of words is extended by the compositional meaning of sentences (DisCoCat model) : the vectors representing words' meanings are composed through the syntactic structure of the sentence. This is done using an algorithm based on tensor products. We see that this algorithm is inefficient on classical computers but scales well using quantum circuits. After exposing the practical details of its implementation, we go through three use-cases.

arXiv:2202.11766•Feb 23, 2022•4 citations

Quantum Algorithms for Compositional Text Processing

Tuomas Laakkonen, Konstantinos Meichanetzidis, Bob Coecke

Quantum computing and AI have found a fruitful intersection in the field of natural language processing. We focus on the recently proposed DisCoCirc framework for natural language, and propose a quantum adaptation, QDisCoCirc. This is motivated by a compositional approach to rendering AI interpretable: the behavior of the whole can be understood in terms of the behavior of parts, and the way they are put together. For the model-native primitive operation of text similarity, we derive quantum algorithms for fault-tolerant quantum computers to solve the task of question-answering within QDisCoCirc, and show that this is BQP-hard; note that we do not consider the complexity of question-answering in other natural language processing models. Assuming widely-held conjectures, implementing the proposed model classically would require super-polynomial resources. Therefore, it could provide a meaningful demonstration of the power of practical quantum processors. The model construction builds on previous work in compositional quantum natural language processing. Word embeddings are encoded as parameterized quantum circuits, and compositionality here means that the quantum circuits compose according to the linguistic structure of the text. We outline a method for evaluating the model on near-term quantum processors, and elsewhere we report on a recent implementation of this on quantum hardware. In addition, we adapt a quantum algorithm for the closest vector problem to obtain a Grover-like speedup in the fault-tolerant regime for our model. This provides an unconditional quadratic speedup over any classical algorithm in certain circumstances, which we will verify empirically in future work.

arXiv:2408.06061•Electronic Proceedings in Theoretical Computer Science•Aug 9, 2024•3 citations

A hybrid classical-quantum workflow for natural language processing

L. ORiordan, Myles Doyle, Fabio Baruffa +1 more

Natural language processing (NLP) problems are ubiquitous in classical computing, where they often require significant computational resources to infer sentence meanings. With the appearance of quantum computing hardware and simulators, it is worth developing methods to examine such problems on these platforms. In this manuscript we demonstrate the use of quantum computing models to perform NLP tasks, where we represent corpus meanings, and perform comparisons between sentences of a given structure. We develop a hybrid workflow for representing small and large scale corpus data sets to be encoded, processed, and decoded using a quantum circuit model. In addition, we provide our results showing the efficacy of the method, and release our developed toolkit as an open software suite.

arXiv:2004.06800•Machine Learning Science and Technology•Sep 30, 2020•36 citations

Quantum Natural Language Processing on Near-Term Quantum Computers

Konstantinos Meichanetzidis, Stefano Gogioso, Giovanni de Felice +3 more

In this work, we describe a full-stack pipeline for natural language processing on near-term quantum computers, aka QNLP. The language-modelling framework we employ is that of compositional distributional semantics (DisCoCat), which extends and complements the compositional structure of pregroup grammars. Within this model, the grammatical reduction of a sentence is interpreted as a diagram, encoding a specific interaction of words according to the grammar. It is this interaction which, together with a specific choice of word embedding, realises the meaning (or "semantics") of a sentence. Building on the formal quantum-like nature of such interactions, we present a method for mapping DisCoCat diagrams to quantum circuits. Our methodology is compatible both with NISQ devices and with established Quantum Machine Learning techniques, paving the way to near-term applications of quantum technology to natural language processing.

arXiv:2005.04147•Electronic Proceedings in Theoretical Computer Science•Sep 6, 2021•88 citations

Quantum Techniques for Optimizing Algorithms in Natural Language Processing

Dalydas Karanath, Udai Shankar

This research paper explores how Natural Language Processing (NLP) algorithms can be enhanced through the use of quantum computing. Since NLP applications such as sentiment analysis, text classification, and machine translation analyze huge volumes of data, the amount of resourceconsuming work for traditional computing architectures, including large scale language models, becomes excessive. There is an opportunity for significant improvements in speed and efficiency because of the quantum properties of superposition and entanglement. This research explores the use of quantum algorithms such as Grover's search, quantum machine learning algorithms, and quantum-inspired tensor networks for alleviating computational NLP bottlenecks. The comparative study of the quantum approach against the classical method shows notable speedup in theory with an explanation of the implementation of quantum algorithms on Noisy IntermediateScale Quantum (NISQ) devices. The most promising NLP algorithm enhancement will most likely come from hybrid quantum-classical sophisticated architectures as discovered through this study, where quantum processing is applied to some components and classical processing is used for the rest of the quantum-classical NLP algorithms. This is the first research study in Quantum Natural Language Processing (QNLP) for real world NLP applications and the author is commended for their efforts.

International Conference on Visual Analytics and Data Visualization (ICVADV)•Feb 24, 2026•0 citations
We propose a new application of quantum computing to the field of natural language processing. Ongoing work in this field attempts to incorporate grammatical structure into algorithms that compute meaning. In (Coecke, Sadrzadeh and Clark, 2010), the authors introduce such a model (the CSC model) based on tensor product composition. While this algorithm has many advantages, its implementation is hampered by the large classical computational resources that it requires. In this work we show how computational shortcomings of the CSC approach could be resolved using quantum computation (possibly in addition to existing techniques for dimension reduction). We address the value of quantum RAM (Giovannetti,2008) for this model and extend an algorithm from Wiebe, Braun and Lloyd (2012) into a quantum algorithm to categorize sentences in CSC. Our new algorithm demonstrates a quadratic speedup over classical methods under certain conditions.
Quantum Natural Language Processing (QNLP) deals with the design and implementation of NLP models intended to be run on quantum hardware. In this paper, we present results on the first NLP experiments conducted on Noisy Intermediate-Scale Quantum (NISQ) computers for datasets of size greater than 100 sentences. Exploiting the formal similarity of the compositional model of meaning by Coecke, Sadrzadeh, and Clark (2010) with quantum theory, we create representations for sentences that have a natural mapping to quantum circuits. We use these representations to implement and successfully train NLP models that solve simple sentence classification tasks on quantum hardware. We conduct quantum simulations that compare the syntax-sensitive model of Coecke et al. with two baselines that use less or no syntax; specifically, we implement the quantum analogues of a “bag-of-words” model, where syntax is not taken into account at all, and of a word-sequence model, where only word order is respected. We demonstrate that all models converge smoothly both in simulations and when run on quantum hardware, and that the results are the expected ones based on the nature of the tasks and the datasets used. Another important goal of this paper is to describe in a way accessible to AI and NLP researchers the main principles, process and challenges of experiments on quantum hardware. Our aim in doing this is to take the first small steps in this unexplored research territory and pave the way for practical Quantum Natural Language Processing.
The main goal of this master's thesis is to introduce Quantum Natural Language Processing (QNLP) in a way understandable by both the NLP engineer and the quantum computing practitioner. QNLP is a recent application of quantum computing that aims at representing sentences' meaning as vectors encoded into quantum computers. To achieve this, the distributional meaning of words is extended by the compositional meaning of sentences (DisCoCat model) : the vectors representing words' meanings are composed through the syntactic structure of the sentence. This is done using an algorithm based on tensor products. We see that this algorithm is inefficient on classical computers but scales well using quantum circuits. After exposing the practical details of its implementation, we go through three use-cases.
Quantum computing and AI have found a fruitful intersection in the field of natural language processing. We focus on the recently proposed DisCoCirc framework for natural language, and propose a quantum adaptation, QDisCoCirc. This is motivated by a compositional approach to rendering AI interpretable: the behavior of the whole can be understood in terms of the behavior of parts, and the way they are put together. For the model-native primitive operation of text similarity, we derive quantum algorithms for fault-tolerant quantum computers to solve the task of question-answering within QDisCoCirc, and show that this is BQP-hard; note that we do not consider the complexity of question-answering in other natural language processing models. Assuming widely-held conjectures, implementing the proposed model classically would require super-polynomial resources. Therefore, it could provide a meaningful demonstration of the power of practical quantum processors. The model construction builds on previous work in compositional quantum natural language processing. Word embeddings are encoded as parameterized quantum circuits, and compositionality here means that the quantum circuits compose according to the linguistic structure of the text. We outline a method for evaluating the model on near-term quantum processors, and elsewhere we report on a recent implementation of this on quantum hardware. In addition, we adapt a quantum algorithm for the closest vector problem to obtain a Grover-like speedup in the fault-tolerant regime for our model. This provides an unconditional quadratic speedup over any classical algorithm in certain circumstances, which we will verify empirically in future work.
Natural language processing (NLP) problems are ubiquitous in classical computing, where they often require significant computational resources to infer sentence meanings. With the appearance of quantum computing hardware and simulators, it is worth developing methods to examine such problems on these platforms. In this manuscript we demonstrate the use of quantum computing models to perform NLP tasks, where we represent corpus meanings, and perform comparisons between sentences of a given structure. We develop a hybrid workflow for representing small and large scale corpus data sets to be encoded, processed, and decoded using a quantum circuit model. In addition, we provide our results showing the efficacy of the method, and release our developed toolkit as an open software suite.
In this work, we describe a full-stack pipeline for natural language processing on near-term quantum computers, aka QNLP. The language-modelling framework we employ is that of compositional distributional semantics (DisCoCat), which extends and complements the compositional structure of pregroup grammars. Within this model, the grammatical reduction of a sentence is interpreted as a diagram, encoding a specific interaction of words according to the grammar. It is this interaction which, together with a specific choice of word embedding, realises the meaning (or "semantics") of a sentence. Building on the formal quantum-like nature of such interactions, we present a method for mapping DisCoCat diagrams to quantum circuits. Our methodology is compatible both with NISQ devices and with established Quantum Machine Learning techniques, paving the way to near-term applications of quantum technology to natural language processing.
This research paper explores how Natural Language Processing (NLP) algorithms can be enhanced through the use of quantum computing. Since NLP applications such as sentiment analysis, text classification, and machine translation analyze huge volumes of data, the amount of resourceconsuming work for traditional computing architectures, including large scale language models, becomes excessive. There is an opportunity for significant improvements in speed and efficiency because of the quantum properties of superposition and entanglement. This research explores the use of quantum algorithms such as Grover's search, quantum machine learning algorithms, and quantum-inspired tensor networks for alleviating computational NLP bottlenecks. The comparative study of the quantum approach against the classical method shows notable speedup in theory with an explanation of the implementation of quantum algorithms on Noisy IntermediateScale Quantum (NISQ) devices. The most promising NLP algorithm enhancement will most likely come from hybrid quantum-classical sophisticated architectures as discovered through this study, where quantum processing is applied to some components and classical processing is used for the rest of the quantum-classical NLP algorithms. This is the first research study in Quantum Natural Language Processing (QNLP) for real world NLP applications and the author is commended for their efforts.