What is Procedural Generation?

Procedural generation encompasses a wide range of computer science techniques that focus on algorithmic content creation. This content can range from expansive video game maps to computer-generated armies in films or even AI-generated art pieces.

Quantum computers have shown promise in executing various procedural generation tasks, including image editing and geopolitical map creation. For more on these topics, you can refer to blog posts authored by our co-author, Dr. James Wootton, available here and here.

A key example of procedural generation, which will be a primary focus of this article, is textual content creation. Text generation can enhance various applications, such as crafting more natural dialogue for non-playable characters in video games and generating automated news articles in journalism.

Our newly developed quantum algorithm, which we will detail soon, is designed for sentence generation. Specifically, it takes a topic as input and produces a brief sentence related to that topic. We will also discuss how a variant of this algorithm can be employed for music generation.

What is NLP?

NLP is a multidisciplinary field that incorporates elements of linguistics, computer science, and artificial intelligence, focusing on how computers interact with human language. The overarching aim of NLP is to enable computers to comprehend text and spoken language similarly to humans. Its applications are diverse, ranging from machine translation and text summarization to chatbot development and spam detection.

Recent advances in quantum algorithms for NLP have led to the emergence of a new research domain called Quantum Natural Language Processing (QNLP). Our quantum sentence generation algorithm builds upon an earlier quantum algorithm used for sentence classification, which categorizes sentences based on their topics. To understand our algorithm fully, we first need to cover the basics of QNLP. For additional insights, you can consult two more blog posts available here and here.

QNLP Basics

To process language on a quantum computer, the first step is to represent sentences using a suitable computational model. In QNLP, we utilize the Distributional Compositional Categorical (DisCoCat) model to capture language meaning. This model allows for the representation of a sentence’s meaning based on both its words and their grammatical relationships, which is a significant advantage over older models that disregard grammatical structure.

DisCoCat facilitates pictorial representations of sentences through string diagrams. In these diagrams, words are depicted as boxes connected by wires that adhere to the formalism of pregroup grammars. Wires are labeled with types, such as “s” for sentences or “n” for nouns. If a type is followed by ".l" or ".r," it indicates that an element of that type is expected on the left (l) or right (r).

For instance, consider the string diagram for the sentence “Alice generates language.” It indicates that the verb “generates” requires one noun on either side. Since both nouns (Alice and language) are present, the diagram shows a single open "s" wire, confirming grammatical correctness.

Interestingly, string diagrams can also be applied to reason about quantum information and computing. While we won't delve into the specifics here, there is an excellent book on this subject available for those interested. For our discussion, it's crucial to understand that each DisCoCat diagram (and thus each sentence) can be converted into a parameterized quantum circuit, with its output encoding the meaning of that sentence. This concept may initially seem complex, so let’s clarify it through sentence classification.

Sentence Classification

As previously mentioned, our quantum sentence generation algorithm builds upon an existing quantum algorithm for sentence classification. Here’s a brief overview of the main steps involved in this algorithm, with more detailed information available in a referenced paper.

1. Annotate a corpus of sentences by assigning them to various topics. For instance, in a dataset of news headlines, topics might include "sports," "politics," "technology," and "entertainment."
2. Convert each sentence into its associated parameterized quantum circuit using a new Python library for QNLP called Lambeq. Note that different circuits may share parameters if they have common words. Measuring a circuit yields a bitstring that corresponds to one of the possible topics. For example, in our news headline dataset, the bitstring “00” might signify “sports,” while “01,” “10,” and “11” indicate “politics,” “technology,” and “entertainment” respectively.
3. Employ classical machine learning methods to optimize parameters so that the measured bitstrings of each quantum circuit align as closely as possible with the annotated topic of that sentence. For example, for the sentence “Real Madrid wins Champions League,” we would aim to obtain the outcome “00,” corresponding to “sports.”
4. For a new sentence outside the original training set, classify its topic by:
   1. Generating the corresponding parameterized quantum circuit using Lambeq.
   2. Measuring the circuit with the optimal parameters identified in step 3.
   3. Outputting the topic corresponding to the resulting bitstring.

Sentence Generation

Now we can describe our sentence generation algorithm. This algorithm treats sentence generation as a combinatorial optimization problem, searching for a sentence that fits a specified topic within a space of all potential sentences.

Here are the steps of the algorithm in detail. We start by assuming that a sentence classifier has been trained using the techniques outlined previously. This classifier enables us to create a generation algorithm that accepts a topic as input and outputs a relevant sentence. For instance, if we request a “sports” headline, the algorithm would proceed as follows:

1. Generate a random initial candidate sentence, such as “Johnson continues new policy,” which we will denote as C.
2. Create the parameterized quantum circuit corresponding to C using Lambeq.
3. Execute this circuit multiple times with the optimal parameters derived in the previous step. The percentage of runs yielding the correct topic bitstring is recorded as P(C). For instance, if the circuit runs 100,000 times and the bitstring “00” (indicating “sports”) appears 12,000 times, then P(C) = 12%.
4. While P(C) remains below a predefined threshold, say 90%, repeat the following loop:
   1. Generate a neighboring sentence, C’, by either inserting a random new word, deleting a word, or replacing a word in C.
   2. If P(C’) > P(C), then update C to C’.

The algorithm described above is a variant of a well-known combinatorial optimization technique called hill climbing. While the actual algorithm we present in our paper employs a more complex method known as simulated annealing, the foundational concepts remain similar.

The following images illustrate an example run of our generation algorithm, which ultimately results in the sentence “Arsenal Continues Winning.”

As shown, we do not necessarily aim to find the absolute best sentence; rather, we seek a satisfactory one. This flexibility is vital to ensure diversity in the generated sentences.

Music Generation

Similar to how a sentence consists of sequential words, a musical piece can be viewed as a series of music snippets arranged together. Below is an example of one such snippet:

Each snippet comprises musical notes, akin to how a word is formed from letters. This analogy was recently explored in a paper that presents a musical adaptation of the DisCoCat framework, using string diagrams to visually depict the composition of short snippets into longer musical works. For instance, the diagram below illustrates a musical composition consisting of snippets p4, p9, p7, and p5.

The overall composition appears as follows:

Now, let’s demonstrate how the algorithms we described for sentences can be adapted for musical composition generation:

To start, we utilize techniques similar to those used for sentence classification to create a music classifier. This classifier is trained on a corpus of 100 musical pieces categorized as either rhythmic or melodic. The dataset is sourced from the Quanthoven GitHub repository. Consequently, the classifier should effectively differentiate between rhythmic and melodic compositions.

Our music generation algorithm mirrors the earlier sentence generation process. When tasked with generating a rhythmic composition, the algorithm follows these steps:

1. Generate a random initial candidate musical composition, denoted as C.
2. Create the corresponding parameterized quantum circuit for C using Lambeq.
3. Execute this circuit multiple times with optimal parameters for our music classifier. Record the percentage of runs that result in the bitstring corresponding to the “rhythmic” class, which we will call P(C).
4. While P(C) is below a certain threshold, repeat the following loop:
   1. Generate a neighboring composition, C’, by inserting, deleting, or replacing a random snippet in C.
   2. If P(C’) > P(C), update C to C’.

Let’s consider a specific example where we instruct our music generation algorithm to create a rhythmic piece. The Python notebook for this instance is available here.

A computer-generated recording of the initial random composition is accessible here:

Upon listening to this recording, it becomes evident that the composition leans more towards melodic than rhythmic. Consequently, our algorithm will continue to refine it by replacing it with better neighboring compositions until a rhythmic one is achieved. After 7 iterations, the candidate composition is:

While this composition demonstrates improved rhythmic qualities, some snippets still retain a melodic feel. Therefore, the algorithm persists in its search for superior compositions.

Finally, after 36 iterations, the algorithm successfully identifies the following composition:

This composition showcases a predominantly rhythmic structure, which is returned as the output of our music generation algorithm.

Conclusion

That wraps up our discussion for today! We’ve explored algorithms that facilitate sentence and short musical composition generation using currently available quantum computers. Why not try them out for yourself?

Before concluding, let's touch on the concept of quantum advantage. This term refers to the potential for quantum algorithms to solve problems more efficiently than classical algorithms. The algorithms we covered are relatively straightforward and should be viewed as proof-of-concept examples indicating that language and music generation is feasible on today’s small, noisy quantum computers. We do not claim they can outperform cutting-edge classical techniques, and thus they do not demonstrate any quantum advantage. However, as organizations like IBM develop more powerful quantum systems, it raises the question of whether we might one day discover quantum algorithms capable of outperforming classical methods in language and music generation. This intriguing open question awaits a definitive answer. If you found this article engaging, perhaps you can help us explore this frontier in the future!