Grover's Question Answering (Quantum Natural Language Processing)

Since the recent rapid development of quantum algorithms, applications of quantum computation in the computational field of Natural Language Processing (NLP) have emerged. Words can be elegantly represented as vectors, matrices, and higher-rank tensors, depending on their grammatical function, that “contract” with each other following grammatical rules. Intuitively, one may wonder whether and where quantum computing could enhance the performance of computational NLP.

Grover’s algorithm, a well-known quantum search algorithm, allows one to find the correct item in a database, with quadratic speedup. Predicting the right answer to a language-based question can be seen from the viewpoint of a search task. The NLP computational task of natural language question answering could therefore benefit from Grover’s algorithm, an idea that is explored in the work we comment on today, which was conducted by researchers at Utrecht University, the Netherlands.

Vector based representation of language structures has been one of the main concepts in NLP, in general. Such representation can be deeply generalized and offers a flexible tool. However, to interpret text fragments considering their grammatical features, while staying in the vector space semantics, the dimension of the representation quickly scales, which has been a limiting feature in vector-based semantics implementations.

In this work, the authors show that a quantum-speedup can be exploited if each word is represented as a quantum state that serves as input to a quantum circuit. In this setting, words are represented as multi-partite quantum states which, when contracted with one another, the meaning of larger text fragments is encoded in the resulting quantum states. This modulates the problem into a search problem, which in turn can be targeted with Grover’s algorithm.

Firstly, text fragments are formed by performing grammar specific quantum measurements that correspond to the contraction of words. Taking quantum states as the representations of all input words, contractions are then identified with the expectation value of an appropriate permutation operator. With this setup, each reading of an ambiguous phrase corresponds to a particular circuit, and different readings are interchangeable upon the application of a number of swap gates. While this addresses the problem of syntactic ambiguities by making use of the quantum superposition principle, ambiguities at the word level can be immediately accommodated for by using density matrices instead of pure states.

The work also demonstrates the formulation of the answers to a “why” question. As input, the algorithm takes a multi-partite state in quantum superposition, representing a why-question and its possible answers, and performs a series of tensor contractions. A series of gates then acts repeatedly on the post-contraction state, guaranteeing that a correct answer to the question is obtained upon a single final measurement. A correct answer is provided using information given directly by the tensor contractions of representations of words without manual feeding of any labels nor to learn the answers to other questions. This translates the learning paradigm into a simple question-answer based class of problems, and presents a scalable approach.

The proposed framework can be used to find a representation for a particular question that contains all the possible answers in equal quantum superposition and allows for the building of an oracle that can detect a correct answer, while being agnostic to the specific question. One obvious advantage of this approach is also that it permits the simultaneous treatment of ambiguous phrases in English, which is allowed in a Grover search problem. Applying Grover’s algorithm to question-answering, turns the representation of the question and answers into the input of the algorithm, together with an oracle that identifies those correct answers. This construction can deal with certain types of ambiguous phrases by keeping the various meanings in quantum superposition.

Further scope of work may focus on finding an effective implementation of the measurement of the permutation operator for an arbitrary number of qubits, possibly making use of the Hadamard test, and understanding how to find a universal form of the inversion operator. This extension of the present formalism can furthermore account for a better understanding of the temporal evolution of the meanings of sentences.