# Quantum Algorithms for Compositional Text Processing

arXiv: https://arxiv.org/abs/2408.06061 · HTML: https://mlsanity.com/paper/2408.06061/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 55 references that are in the map.
- First posted on arXiv 12 Aug 2024.

## Builds on (most cited first, 21 of 21)

- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks](https://mlsanity.com/paper/1502.05698/) (2015)
- [Towards Quantum Machine Learning with Tensor Networks](https://mlsanity.com/paper/1803.11537/) (2018)
- [QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer](https://mlsanity.com/paper/2102.12846/) (2021)
- [Foundations for Near-Term Quantum Natural Language Processing](https://mlsanity.com/paper/2012.03755/) (2020)
- [lambeq: An Efficient High-Level Python Library for Quantum NLP](https://mlsanity.com/paper/2110.04236/) (2021)
- [Quantum Natural Language Processing on Near-Term Quantum Computers](https://mlsanity.com/paper/2005.04147/) (2020)
- [Seeing is Believing: Brain-Inspired Modular Training for Mechanistic Interpretability](https://mlsanity.com/paper/2305.08746/) (2023)
- [Criticality in Formal Languages and Statistical Physics](https://mlsanity.com/paper/1606.06737/) (2016)
- [CompactifAI: Extreme Compression of Large Language Models using Quantum-Inspired Tensor Networks](https://mlsanity.com/paper/2401.14109/) (2024)
- [The Frobenius anatomy of word meanings I: subject and object relative pronouns](https://mlsanity.com/paper/1404.5278/) (2014)
- [Quantum Algorithms for Compositional Natural Language Processing](https://mlsanity.com/paper/1608.01406/) (2016)
- [The Mathematics of Text Structure](https://mlsanity.com/paper/1904.03478/) (2019)
- [Grammar-aware sentence classification on quantum computers](https://mlsanity.com/paper/2012.03756/) (2020)
- [Compositionality as we see it, everywhere around us](https://mlsanity.com/paper/2110.05327/) (2021)
- [Conversational Negation using Worldly Context in Compositional Distributional Semantics](https://mlsanity.com/paper/2105.05748/) (2021)
- [Distilling Text into Circuits](https://mlsanity.com/paper/2301.10595/) (2023)
- [Near-Term Advances in Quantum Natural Language Processing](https://mlsanity.com/paper/2206.02171/) (2022)
- [A quantum teleportation inspired algorithm produces sentence meaning from word meaning and grammatical structure](https://mlsanity.com/paper/1305.0556/) (2013)
- [A Pipeline For Discourse Circuits From CCG](https://mlsanity.com/paper/2311.17892/) (2023)
- [Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm](https://mlsanity.com/paper/2112.02040/) (2021)

## Built on by (most cited first, 3 of 3)

- [Quantum computing and artificial intelligence: status and perspectives](https://mlsanity.com/paper/2505.23860/) (2025)
- [Quantum Natural Language Processing: A Comprehensive Review of Models, Methods, and Applications](https://mlsanity.com/paper/2504.09909/) (2025)
- [Efficient Generation of Parameterised Quantum Circuits from Large Texts](https://mlsanity.com/paper/2505.13208/) (2025)

## Abstract (arXiv)

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.