An introduction to Quantum Natural Language Processing
By Amin Karamlou, Marcel Pfaffhauser, and James Wootton
Today we’re going to talk about how you can use IBM Quantum computers for generating natural language and music. We’ve made the Python notebook for generating the pieces of music used as examples in this post available on our GitHub repository. Feel free to use them for generating your own pieces, it can be quite fun! We’ll keep things pretty high level but you can check out our paper available here for more details. You can also watch a recording of our talk at the 2022 Quantum Natural Language Processing conference here.
Much of what we’ll cover is related to Natural Language Generation (NLG), which is a topic at the intersection of procedural generation and Natural Language Processing (NLP). Before we dive into the details of our own work, it’s worth discussing what these fields are about (And we’ll say it again later: but note that this is just a proof of concept).
If you want to learn more about QNLP you can watch the talk in the Qiskit Seminar Series: https://www.youtube.com/watch?v=pFc2PmxVMt8
What is Procedural Generation?
Procedural generation is a broad area of computer science that focuses on the algorithmic generation of content using computers. The generated content can be anything from large maps used in video games, to CGI armies used in movies, or even AI-generated pieces of art.
Quantum computers have already been successfully used for some procedural generation tasks, including image manipulation, and geopolitical map creation. Both of these topics have their own blog posts written by our coauthor Dr. James Wootton, available here and here.
Another important example of procedural generation which will be a major focus of this blog post is the generation of textual content. Text generation has a wide variety of applications — for instance, in the creation of more natural sounding dialogue for non-playable characters in video games, or for the generation of automatic news articles in journalism.
Our new quantum algorithm which we will shortly describe performs the task of sentence generation. More precisely it takes a topic as input, and generates a short sentence about that topic as an output. We’ll also talk about how a variant of this algorithm can be used for music generation.
What is NLP?
NLP is an area of study with elements from linguistics, computer science and artificial intelligence that focuses on the interaction between computers and human language. Loosely speaking the goal in NLP is to make computers capable of understanding text and spoken language in much the same way that humans do. NLP has countless use cases such as machine translation, text summarization, chatbot creation, and spam detection.
Recent interest in the creation of quantum algorithms for NLP has given birth to a new field of research, which is now known as quantum natural language processing (QNLP). Our quantum sentence generation algorithm builds on top of an earlier quantum algorithm for sentence classification, where the goal is to classify the topic of a given sentence. For this reason, before we can talk about our algorithm, we must go over some of the basics of QNLP. For more details about QNLP you can refer to two further blog posts available here and here.
QNLP Basics
The first task, if we want to process language on a quantum computer, is to represent sentences in a fitting computational model. In QNLP, the Distributional Compositional Categorical (DisCoCat) model of language meaning is used for this purpose. The reason is that DisCoCat allows for the meaning of a sentence to be described based not only on its words, but also their grammatical relationship. This is an advantage over some older models which treat sentences as a bag of unordered words and ignore their grammatical structure.
DisCoCat allows any sentence to be represented in pictorial fashion with the help of so-called string diagrams. In these diagrams, words are represented using boxes, and wires connect these boxes according to the formalism of pregroup grammars. Wires are annotated by types, for instance “s” for a whole sentence, or “n” for noun. If a letter is followed by a “.l” or a “.r” this means that an element of that type is expected either on the left (l) or right (r).
Let’s take the diagram for the sentence “Alice generates language” as an example which we can see in the figure above. We read this diagram as follows: The word “generates” expects one noun to the left and a noun to the right. Since it is provided with both these nouns (Alice and language) there is only a single open “s” wire in the diagram which shows that the whole sentence is grammatically correct.
As it turns out, string diagrams can also be used to reason about quantum information and quantum computing. We won’t go over what this means in detail but if you are interested, there is a fantastic book on this topic available here. For our purposes it suffices to say that this connection means that any DisCoCat diagram (and thus any sentence) can be transformed into a parameterized quantum circuit whose output encodes the meaning of that sentence. This concept may seem a bit cryptic at first so let’s try to understand what it means by discussing sentence classification.
Sentence classification
As we already mentioned, our quantum sentence generation algorithm builds on top of an existing quantum algorithm for sentence classification. We briefly outline the main steps of this algorithm now. You can read more details in a paper available here.
1. Start by annotating a corpus of sentences as belonging to one of several possible topics. For example, if the sentences are news headlines, the topics could be “sports”, “politics”, “technology”, and “entertainment”.
2. Convert each sentence to its corresponding parameterized quantum circuit. This can be done with the help of a new Python library for QNLP known as Lambeq. Note that different circuits will share parameters if they share words. Measuring a circuit returns a string of bits which corresponds to one of the possible topics. In our news headline example, we might have that the bitstring “00” corresponds to “sports”, while the bitstrings “01”, “10”, “11”, correspond to “politics”, “technology”, and “entertainment” respectively.
3. We use classical machine learning techniques to find optimal parameters such that the measured bitstrings of each quantum circuit correspond as much as possible with the annotated topic of that sentence. For example, if we measure the circuit corresponding to the sentence “Real Madrid wins Champions League”, we would want to obtain the outcome “00” which corresponds to “sports”.
4. Finally, given a new sentence that does not belong to the initial training corpus, we can classify it’s topic as follows:
a. Generate the corresponding parameterized quantum circuit using Lambeq.
b. Measure the parameterized quantum circuit using the optimal parameters found in step 3.
c. Output the topic corresponding to the measured bitstring.
Sentence generation
We can now finally explain our sentence generation algorithm. This algorithm works by treating sentence generation as a combinatorial optimization problem. This means that it works by searching for a sentence with the correct topic in a search space of all possible sentences.
Let’s explain some of the details of this algorithm. We first assume that we have trained a sentence classifier using the techniques described in the previous section. Using this we can create a generation algorithm which takes as an input one of the topics that this sentence classifier is trained over, and returns as an output a sentence with that topic. For instance, in our news headlines example we could ask the algorithm to generate, say, a “sports” headline. The algorithm would then proceed as follows:
1. Generate a random initial candidate sentence. This could be the sentence “Johnson continues new policy”. Let us call this sentence C.
2. Create the parameterized quantum circuit corresponding to C using Lambeq.
3. This circuit is run many times with the optimal parameters obtained in step 1. The percentage of the runs where the outputted bitstring corresponds to the correct topic is recorded. Let us call this value P(C). So, if we run the circuit 100000 times and observe the bitstring “00” which corresponds to “sports” 12000 times P(C) = 12%.
4. While the value P(C) is less than some threshold, say, 90%, perform the following actions in a loop.
a. Generate a “neighboring” sentence of C called C’ by either inserting a new random word into C, deleting a random word from C or replacing a random word from C with a new random word.
b. If P(C’) > P(C) then set C = C’.
The algorithm we have described above is a variant of a well-known technique for solving combinatorial optimization problems known as hill climbing. The actual algorithm we describe in our paper is a slightly more complicated technique known as simulated annealing, but the main ideas are quite similar.
The pictures that follow show an example run of our generation algorithm which eventually outputs the sentence “Arsenal Continues Winning”.
As you see we do not necessarily require finding the best sentence, but just want to find one, which is good enough. This is important, to make sure we do not always generate the exact same sentence.
Music generation
Just like how a sentence is composed of words placed side by side, a musical composition can be seen as a sequence of music snippets placed next to each other. Here’s an example of one of these snippets:
As you can see each snippet itself is composed of musical notes, similar to how a word is composed of letters belonging to an alphabet. This similarity was recently used in a paper available here to create a musical version of the DisCoCat framework, where string diagrams are used to pictorially represent the composition of short snippets into longer pieces of music. The diagram below for example represents a musical composition which consists of the 4 snippets p4, p9, p7, p5.
The composition as a whole looks like this:
Now let’s show with the help of an example how the algorithms we described previously for sentences can be adapted and used to generate musical pieces:
To begin with, we use very similar techniques to what we used for sentence classification to create a music classifier. We train this classifier on a corpus of 100 musical compositions annotated as being either rhythmic or melodic. This corpus was taken from the Quanthoven GitHub repository. Thus, given a musical composition that is either rhythmic or melodic, our classifier should be able to distinguish which one of these two classes it belongs to.
Our music generation algorithm can now be defined similarly to the earlier sentence generation algorithm. If we ask the algorithm to generate a composition that is rhythmic it proceeds as follows:
1. Generate a random initial candidate musical composition. Let us call this composition C.
2. Create the parameterized quantum circuit corresponding to C using Lambeq.
3. This circuit is run many times with the optimal parameters for our music classifier. The percentage of the runs where the outputted bitstring corresponds to the “rhythmic” class is recorded. Let us call this value P(C).
4. While the value P(C) is less than some threshold, perform the following actions in a loop:
a. Generate a “neighboring” composition of C called C’ by either inserting a new random snippet into C, deleting a random snippet from C or replacing a random snippet from C with a new random snippet.
b. If P(C’) > P(C) then set C = C’.
Let’s look at an actual example where we ask our music generation algorithm to create a rhythmic piece of music. The Python notebook for this example is available here.
A computer-generated recording of the random initial composition is given here:
If you listen to this recording, it is clear that the composition is far more melodic than rhythmic. So, our algorithm will keep replacing it with better neighboring compositions until a rhythmic one is found. After 7 iterations the candidate composition is here:
While this is a noticeably more rhythmic composition, there are still certain snippets of the composition that feel quite melodic. Hence our algorithm continues looking for better compositions.
Finally, after 36 rounds the algorithm finds the following composition:
This composition is almost entirely rhythmic and is thus returned as the output of our music generation procedure.
Conclusion
That’s all we had for you today folks! We’ve talked about some algorithms which allow you to generate sentences and short musical compositions on quantum computers that are available right now. Why are you even still here!? Go try them out!
Before we wrap up, let’s say a couple of words about quantum advantage. This term refers to the ability of quantum algorithms to solve problems faster than classical algorithms. The algorithms we discussed today are very simple, and should only be seen as proof-of-concept examples that language and music generation can be performed even on today’s small and noisy quantum computers. We are by no means claiming that they can outperform state-of-the-art classical techniques — thus, they don’t exhibit any quantum advantage. However, as companies such as IBM build more powerful quantum computers, it is natural to ask whether we can one day find quantum algorithms for generating language and music that do outperform classical techniques. This is a fascinating open question that doesn’t have a clear answer yet. If you’ve enjoyed this blog post, then maybe you can help us to settle it one day.
