# Grover's Algorithm for Question Answering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 37 references that are in the map.
- First posted on arXiv 9 Jun 2021.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer](https://mlsanity.com/paper/2102.12846/) (2021)
- [Distributional Semantics and Linguistic Theory](https://mlsanity.com/paper/1905.01896/) (2019)
- [Foundations for Near-Term Quantum Natural Language Processing](https://mlsanity.com/paper/2012.03755/) (2020)
- [Quantum Natural Language Processing on Near-Term Quantum Computers](https://mlsanity.com/paper/2005.04147/) (2020)
- [The Mathematics of Text Structure](https://mlsanity.com/paper/1904.03478/) (2019)
- [Open System Categorical Quantum Semantics in Natural Language Processing](https://mlsanity.com/paper/1502.00831/) (2015)
- [Lambek vs. Lambek: Functorial Vector Space Semantics and String Diagrams for Lambek Calculus](https://mlsanity.com/paper/1302.0393/) (2013)
- [Modelling Lexical Ambiguity with Density Matrices](https://mlsanity.com/paper/2010.05670/) (2020)
- [Sentence Entailment in Compositional Distributional Semantics](https://mlsanity.com/paper/1512.04419/) (2015)
- [A State of the Art of Word Sense Induction: A Way Towards Word Sense Disambiguation for Under-Resourced Languages](https://mlsanity.com/paper/1310.1425/) (2013)
- [Incremental Monoidal Grammars](https://mlsanity.com/paper/2001.02296/) (2020)
- [Putting a Spin on Language: A Quantum Interpretation of Unary Connectives for Linguistic Applications](https://mlsanity.com/paper/2004.04128/) (2020)

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

- [Implications of Deep Circuits in Improving Quality of Quantum Question Answering](https://mlsanity.com/paper/2305.07374/) (2023)
- [Traitement quantique des langues : 'etat de l'art](https://mlsanity.com/paper/2406.15370/) (2024)

## Abstract (arXiv)

Grover's algorithm, a well-know quantum search algorithm, allows one to find the correct item in a database, with quadratic speedup. In this paper we adapt Grover's algorithm to the problem of finding a correct answer to a natural language question in English, thus contributing to the growing field of Quantum Natural Language Processing. Using a grammar that can be interpreted as tensor contractions, each word is represented as a quantum state that serves as input to the quantum circuit. We here introduce a quantum measurement to contract the representations of words, resulting in the representation of larger text fragments. Using this framework, a representation for the question is found that contains all the possible answers in equal quantum superposition, and allows for the building of an oracle that can detect a correct answer, being agnostic to the specific question. Furthermore, we show that our construction can deal with certain types of ambiguous phrases by keeping the various different meanings in quantum superposition.