Near-Term Advances in Quantum Natural Language Processing]Near-Term Advances in Quantum Natural Language Processing

Dominic<EMAIL_ADDRESS>Aaranya Alexander
Daiwei Zhu
Chase Zimmerman
Arunava Majumder

IonQ Inc., College Park, Maryland, USA Preprint from 2023. See <https://link.springer.com/article/10.1007/s10472-024-09940-y> for updated official version

This paper describes experiments showing that some tasks in natural language
processing (NLP) can already be performed using quantum computers, though so far only with small datasets.

We demonstrate various approaches to topic classification.
The first uses an explicit word-based approach, in which word-topic  weights are
implemented as fractional rotations of individual qubits, and a phrase is classified
based on the accumulation of these weights onto a scoring qubit using entangling quantum gates.
This is compared with more scalable quantum encodings of word embedding vectors, which are used
to compute kernel values in a quantum support vector machine: this approach achieved
an average of 62% accuracy on classification tasks involving over 10000 words, which is
the largest such quantum computing experiment to date.

We describe a quantum probability approach to bigram modeling that can be applied to understand sequences of words and formal concepts,
investigate a generative approximation to these distributions using a quantum circuit Born machine, and introduce
an approach to ambiguity resolution in verb-noun composition using single-qubit rotations for simple nouns and
2-qubit entangling gates for simple verbs.

The smaller systems presented have been run successfully on physical
quantum computers, and the larger ones have been simulated.
We show that statistically meaningful results can be obtained,
but are much more difficult to predict using real datasets than
using artificial language examples from previous quantum NLP research.

Related NLP research is compared, partly with respect to contemporary
challenges including informal language, fluency, and truthfulness.

§ INTRODUCTION

Natural Language Processing (NLP) is a promising area of application using quantum computers.
This paper reports on progress in developing and running
NLP experiments on trapped-ion quantum computers mainly during the year 2022. The experimental applications include
topic classification, bigram modeling, and ambiguity resolution.

More generally, building real artificial general intelligence is a core goal of computer science.
Reasons for believing that quantum models and quantum computing
may contribute to building more fully intelligent systems are varied,
and are discussed in Section <ref>.
Our approach to building early-stage language processing systems
on quantum computers is motivated by these goals. Questions this entails include:
what properties are lacking in artificial intelligence (AI) today; whether these gaps
can be addressed with quantum approaches;
what core mathematical / language operations can be identified; and
for each operation, what are the simplest effective implementations?
These questions help to motivate medium-term challenges and immediate progress.

The examples presented in this paper include word-based topic classification in Section
<ref>, bigram sequence modelling in Section <ref>,
and ambiguity resolution in verb-noun composition in Section <ref>.
Progress in related systems and fields is surveyed in Section <ref>,
focusing partly on the question of whether natural language grammar and syntax needs
to be modeled explicitly in quantum NLP. Thanks partly to progress with more mainstream NLP language models,
we argue that factual accuracy is more central and challenging than aligning semantics with syntax explicitly.
The conclusion in Section <ref> revisits core questions in scale and accuracy:
our experiments have processed large enough real datasets to produce statistically meaningful results,
though considerably smaller than would be needed to compete with standard classical methods on natural language data.

§ THE PROMISE OF QUANTUM NLP

Overlaps between quantum theory and NLP are many and varied, ranging from structural and qualitative
similarities to directly sharing mathematical techniques.

§.§ Structural Similarities

Language and quantum mechanics have notable qualitative similarities [1].
Most words have several possible meanings or could refer
to several different things. Even if we can predict the range of options in advance, we do not typically know which interpretation
of a word or phrase is appropriate until we encounter it in context. However, once a word is observed
in context, one of the available meanings is typically selected, and this selection tends to remain fixed until the context changes.
Similarly, quantum mechanics predicts the probabilities of different outcomes, not which outcome is actually found, unless the system is already in a fixed state that is aligned with the measurement being performed. When measured, the system is observed to be
in a fixed state, and if measured again, the same result will be given — the outcome remains fixed until something changes it
<cit.>. Even if we prefer precise deterministic theories in physics and linguistics, nature and language are
unpredictable in practice.

Features found in quantum theory have been explored in other human sciences, noting similar patterns.
The nature of money in economics and finance is one example: David Orrell's textbook Quantum Economics and Finance argues that
credits and debts show similarities to the concept of quantum entanglement, and that
money, price, and value are uncertain properties that only become fixed when they are agreed and recorded in
transactions, likening the former to quantum and the latter to classical information 3. Cognitive scientists have
measured relationships between available information, context, and decision-making, that violate
classical probabilistic laws but can be represented concisely and accurately as phase interference terms in
quantum models [4].

Such similarities do not show us how to perform particular language processing tasks, but
they do suggest that there is a rich space to explore, which is especially inviting for problems involving
large amounts of context and uncertainty which frustrate classical or more reductionist approaches.
For some human problems, if we look to mathematics and physics for helpful techniques,
quantum mechanics and logic can be just as intuitive a place to start as classical mechanics and logic.

§.§ Compositional Behaviors

Language is compositional, in the sense that the meanings of new phrases and sentences can be derived from their parts,
even when the phrase itself has not been seen before or describes something quite unrealistic.
For example, one may have never heard the phrase “purple polar bear” before,
but it immediately conjures up a mental picture of a polar bear whose color is purple.

Language composition sometimes produces similar structures from dissimilar ingredients — for example, in the context
of hotels, “book a room” and “make a reservation” have overlapping and sometimes identical meanings, even though
neither of the pairs (book, make) or (room, reservation) are usually synonyms. The phrases nonetheless
make immediate sense to familiar listeners, at which point it becomes harder to decompose the phrase into its constituents.
Perhaps the word “book” is there because there used to be physical books that such plans was written down in, and at that
point the reservation was “booked”. The claim here is not that this is the true etymology, but that the exercise of looking
for such a piecewise explanation is itself unusual for us.

Schrödinger [5] famously noted a similar phenomenon in quantum mechanics:

When two systems, of which we know the states by their respective representatives, enter into temporary physical interaction due to known
forces between them, and when after a time of mutual influence the systems separate again, then
they can no longer be described in the same way as before, viz. by endowing each
of them with a representative of its own. I would not call that one but rather the
characteristic trait of quantum mechanics, the one that enforces its entire
departure from classical lines of thought.

Similar patterns have been noted for centuries — for example, Aristotle (De Interpretatione, Ch 2)
argues that in the common phrase “a fair steed”, the word “steed” has an independent meaning, but in the proper name “Fairsteed”, it does not.
[The words Aristotle uses are
greek Κάλιππσς
contrasted with
καλός ἵππος,
greek καλός  as in `calligraphy' and
greek ἵππος  as in `hippodrome' or `hippopotamus',
so the correspondence with English `fair steed' is quite direct <cit.>.]
Given the prevalence of composition as a general topic, one might ask whether any overlap between language and quantum
mechanics here is just accidental. One mathematical approach to answering this question has been to explore common
compositional structures using category theory. This has become a fertile direction for research, because common
structures have been identified (in particular, compact closed categories), and moreover, this has shown ways in which
various grammatical and lexical structures can be represented and even combined into tensor networks
that can be implemented as quantum circuits [7, 8].

§.§ Vectors Everywhere

Vectors and linear algebra have become ubiquitous throughout artificial intelligence, including NLP.
Important cases include the use of feature vectors in statistical machine learning, and the
representation of states and operators in neural networks [9]. Linear algebra is also
central to quantum mechanics and quantum computing <cit.>.

Again one may ask whether these overlaps are significant — the use of vectors alone might be a shallow
commonality. But many more pieces of quantum mathematics have been found to useful in language-related
tasks, including subspaces and projections for representing conditionals [11] and
logical negation and disjunction [12], quantum probability and the analysis of off-diagonal
correlations for information retrieval [13], entanglement for representing the
combined representation of many pairwise relationships [14].

Comparing Quantum (left) with Boolean Logic (right). In quantum logic concepts are modelled
by subspaces such as lines and planes, and a point can be projected onto any subspace. In classical logic
concepts can be represented by any set of points, and a point either belongs to this set or it does not.

While vector spaces have become ubiquitous in AI, some of the opportunities they present have remained comparatively unused.
For example, the lattice of subspaces (lines, planes, and higher-dimensional versions of these) provides a geometric model
for a kind of logic, just as set theory gives a model for Boolean logic (Figure <ref>). This was discovered by
Garrett Birkhoff and John von Neumann in the 1930's
and given the name “quantum logic” [15]. In terms of operator algebras, the subspaces are in one-to-one
correspondence with the lattice of projectors onto those subspaces, and projections move points around the space.
This gives quantum logic a non-local character, which can be exploited for semantic modelling. The negation
operator in quantum logic is projection onto the orthogonal subspace — for example, in Figure <ref>,
“p  (A  B)” would be represented as the orthogonal projection of the point $p$ onto
the line $C$, since $C$ is orthogonal to the plane spanned by $A$ and $B$. This form of vector negation can be used to navigate
between different areas of meaning, rather than just removing unwanted items piecemeal <cit.>.
Several techniques that have been adapted from earlier quantum literature and applied to problems in AI today.
Many of the successes of
quantum mathematics in artificial intelligence are surveyed by Widdows et al [16].

§.§ The Availability of Quantum Computers

Far from being considered popular or fashionable, research using quantum mathematical models outside of conventional platforms of quantum physical systems such as isolated atoms have often been met with skepticism and resistance — perhaps because quantum theory is too-often overhyped
and speculative in general science writing, and in some cases because clinging to classical determinism is considered to
be much more scientifically respectable <cit.>.

These hurdles may be becoming easier to surmount — for example, major journals have recently published papers
on quantum approaches in areas including at least economics [17],
psychology [18], and AI [16]. Reasons for this acceptance include
the reality of quantum hardware. Working quantum computers have been built and are running programs every day
— in a development process spanning decades, concepts like “entangled pairs” have gone
from scientific imagination through experimental demonstration to engineering implementation. We may be
uncomfortable with such quantum concepts, but unlike pioneers in the 1930's, we have evidence that resolves any reasonable
dispute about their reality.

The question for quantum approaches is no longer “Are they real?” but “Are they useful?”.
In NLP the work is still in its early days, and success must be demonstrated by building useful systems.
Rather than predicting a singular quantum advantage
for a particular quantum NLP system, this paper explores several examples, with an eye to general capabilities.
The next few sections give examples of how standard
language processing tasks have been successfully performed on quantum computers.
Experiments below used the 11-qubit trapped ion quantum computer described by Johri et al. [19],
and where necessary, the larger IonQ Aria machine with a capacity of 32 physical and 20 algorithmic qubits [20]. A crucial point to bear in mind with quantum computing is that the memory capacity
of a system doubles every time a qubit is added, because the number of basis vectors that can be combined
in superposition doubles. While this memory is difficult to
access in practice and comes with caveats and restrictions, just the notion of exponential memory
growth is a compelling attraction for researchers in data-hungry fields like NLP [16].

Basic quantum logic gate diagrams used throughout these examples. A single qubit rotation gate (left)  manipulates superposition of $\ket{0}$ and $\ket{1}$ states for the qubit. The two-qubit CNOT gate (right) entangles two qubits

Some familiarity with Dirac's bra-ket notation, quantum bits (qubits), gates, and circuits is necessary to fully understand the experiments presented in this paper.
For a thorough review of this area, see Nielsen and Chuang <cit.>. Alternatively, the more introductory presentation
found in Orrell's textbook <cit.> is enough to understand the new circuits presented below.
A qubit is a two-level quantum system, whose basis states are normally written as $\ket{0}$ and $\ket{1}$,
and whose pure states are superpositions of the form $\lambda\ket{0} + \mu\ket{1}$, where $\lambda$ and $\mu$
are complex numbers with $\vert\lambda\vert^2 + \vert\mu\vert^2 = 1$. Thus the state of a qubit is represented by a vector in $\mathbb{C}^2$.
When $n$ qubits are assembled, their combined state is represented by the tensor product
$\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \ldots \otimes \mathbb{C}^2 \equiv (\mathbb{C}^2)^{\otimes n}
\cong \mathbb{C}^{(2^n)}$.
The key gate operations are
single-qubit gates which manipulate the coefficients $\lambda$ and $\mu$ for a single qubit,
and two-qubit gates, in particular the `controlled-X' or `controlled-NOT' (CNOT) gate that perfoms an X-rotation on the second qubit
of the first qubit is in the $\ket{1}$ state.  Example circuit diagram components for these are shown in Figure <ref>.
Readers for whom these are at least somewhat familiar should be able to understand most of the subsequent examples in this paper.
Readers for whom these are new are encouraged to consult one of the textbooks cited or online
resources.[See e.g., <https://en.wikipedia.org/wiki/Quantum_logic_gate> and <https://qiskit.org/learn/> c.f. [21].]

§ WORD-BASED TOPIC CLASSIFICATION AND STATE ADDITION

Text classification or topic classification is the task of assigning topic labels to texts such as sports or music,
or in the case of “Which bands performed at the Super Bowl this year?”, perhaps both. It has many uses including
intent classification in dialog systems, assigning topic keywords to documents, routing incoming messages
for customer service, and spam filtering. There are many successful methods, often involving vector representations
and various forms of neural networks and dimensionality reduction [22].

§.§ One Qubit Per Word and Topic

The quantum implementation developed here was deliberately simple: a bag-of-words classifier on a quantum computer.
In this context, `bag-of-words' means that only individual words are used as features for the classifier:
the order of words is not taken into account, or even which combinations of words appear. So for example, a bag-of-words classifier
may predict that a document containing the word horse is about farming or sports, which will often
be correct, but is a mistake if it occurs in the phrase “A horse chestnut is a deciduous tree with palmate leaves.”

The training process for such a classifier is usually some form of supervised machine learning. A collection of texts or documents is sampled,
labels are applied to these texts by human annotators, and these examples are used to train the classifier to deal with
new unseen examples. For a bag-of-words classifier, a simple version of this process is:

* For each (document, topic) pair in the training set, split the document text into a list of words.

* For each word in that list, increment a score recording how often this word was seen with this topic.

This process gradually builds up a term-topic matrix (if each document is considered to be a distinct topic,
this is exactly the same as a term-document matrix). The classification stage then proceeds as follows:

* A new document is passed to the classifier. It is split into a list of words.

* For each word, look up the scores that word acquired for each topic during training.

* Given each topic an overall score accumulated from the sum of the scores for each word.

* Choose the topic with the highest score as the overall winner.

This example was chosen because it raises some basic mathematical implementation questions — in particular,
item <ref> in training, “How do we keep a score for each (word, topic) pair?” and
item <ref> in classification, “How do we accumulate an overall score from these individual contributions?”
The first of these problems can be addressed using repeated single-qubit rotations, and the second by connecting
the rotated qubits to a common `sum qubit', as shown in Figure <ref>.
A detailed analysis of the gate matrices in Figure <ref> shows that the probability of
measuring a state $\ket{1}$ in the sum qubit $q_2$ is given by $\sin^2(\theta)\cos^2(\varphi) + \cos^2(\theta)\sin^2(\varphi)$.
This is the case when the input rotations are $X$-rotations <cit.>. Using other fractional rotations
as generators gives combinations with different algebraic properties, investigated more thoroughly in a mathematical paper by Widdows
[23]. Most generally, if the two single-qubit rotations
in Figure <ref> are represented by the matrices

\begin{equation*}
\textbf{A} = \begin{bmatrix}  \alpha & \beta \\ -\ov{\beta} & \ov{\alpha} \end{bmatrix} \quad \mathrm{and} \quad
\textbf{B} = \begin{bmatrix}  \gamma & \delta \\ -\ov{\delta} & \ov{\gamma} \end{bmatrix},
\label{qsum2_eqn}
\end{equation*}

\[P(q_2 = \ket{1}) = \vert\alpha\ov{\delta}\vert^2 + \vert\ov{\beta}\gamma\vert^2. \]

Example Adder Circuit that Combines the Angles $\theta$ and $\varphi$

The bag-of-words classifier is built by assembling several such qubits and gates.
During training, each (word, topic) pair
is assigned to a particular qubit, and the (word, topic) weights are accumulated by scanning over the
training set and incrementing the rotation for the corresponding qubit every time a given
word occurs with a given topic. For each topic, an extra qubit is declared to keep the sum for each topic,
so the number of qubits required is $(\mathrm{num\_words + 1})\times \mathrm{num\_topics}$.
(Hence this design only works as a demonstration for very small vocabularies.)
During classification of a new phrase, each recognized
word in the phrase has each of its topic weights connected to the sum qubit for that topic.

As a worked example, consider the toy training corpus:

I play football     $\rightarrow$     sports

I play guitar     $\rightarrow$     music

The training process records that the content word football gives a score to sports and guitar gives a score to music
(assuming a preprocessing step that notes that the other words are common to all topics.)
When classifying the phrase “Do you want to play football?”, the word football is recognized and each of the football, topic
weights are connected to the sum qubit for the corresponding topic. Each of the topic qubits is measured, and the winner is the topic
that measures the most $\ket{1}$ states over a number of shots. A circuit implementing this process is shown in Figure <ref>.

Example Classification Circuit for Two Words and Two Topics

§.§ One Qubit Per Embedding Dimension

The design above is clear but wasteful — a system that requires distinct bits for each word in the vocabulary would be fine in classical
but not yet in quantum computing. In machine learning terms, using a qubit for each word is an example of a `one-hot encoding',
and to avoid redundancy and get more information out of each dimension, more compact distributional vector embeddings are often preferred. The work by Alexander and Widdows [24] details the method used to classify words from their vector embeddings using a quantum support vector machine (QSVM), and demonstrates subsequent experiments for different QSVM implementations. The steps used in the paper are summarized as follows, and results are explored in further sections.

First, the Word2Vec technique was used [25] to reduce the representation of each word to 8 dimensions.
This part of the process was run classically as a preprocessing step. The generated vectors were then used as input parameters for a feature map quantum circuit. Measurement of the feature map yields a value representing the relationship between two word vectors, which is stored in a kernel matrix [26]. This kernel was then used as input for a quantum support vector machine.
For this experiment, the  and  implementations from the Qiskit package were used [21],
as shown in Figure <ref>. The  applies Hadamard gates on each qubit (denoted by $H$) and a parameterized unitary gate ($U_{\phi}$) in a repetitive cycle; details regarding meaning behind this structure can be found in a preliminary QSVM paper by Havlicek et al [26]. The first half of the feature map circuit will use parameters from one word vector, and the second half will take parameters from another word vector.

SVM Kernel Circuit Example with 8-Dimensional Inputs \(\vec{x}\) and \(\vec{z}\)

§.§ N Qubits for 2N̂ Embedding Dimensions

Densely-encoded Kernel Circuit with 8-Dimensional Inputs

Building off of an $n$-qubit feature map for $n$-dimensional word vectors, the same QSVM classification process was followed for densely encoded feature maps [24]. In this case, vector representations were encoded into fewer qubits in the feature map circuit, using \(\log_{2}(n)\)-qubits for $n$-dimensional word vectors. Using such a mapping reduces qubit use without necessarily compromising the complexity of information represented in the word embeddings, as shown in Figure <ref>.

As observed in the results below, the classical embeddings preprocessing step from Section <ref> enabled
the quantum circuit to achieve relatively high accuracy with fewer qubits. Further improvements to space using densely encoded feature maps achieved similar results.

§.§ Data and Experimental Results

For our initial small-scale experiments, the test and training
datasets from the  package were used [27], which was previously used for the evaluation of the
compositional quantum NLP system of Lorenz et al [28]. This dataset consists of 70 training sentences and 30 development and test sentences, artificially generated to use a small fixed vocabulary and to follow predictable syntactic patterns.
Lorenz et al.28 report an accuracy of 83.3% on the test dataset using a 6-qubit quantum computer, and a similar work by Kartsaklis and Sadrzadeh [27]
report achieving 100% accuracy after several rounds of training on a noisy simulation of a quantum computer.
These are the nearest comparable experiments to those reported here, so the same dataset was deliberately reused.

Both the “one qubit per word and topic classifier” of Section <ref> was able to reach 100% accuracy,
and the word embeddings classifiers of
Section <ref> and Section <ref> were able to reach 90-100% accuracy, with comparatively little training and tuning.

For the bag-of-words classifier of Section <ref>,
the key parameters to tune were the number of words to use and the incremental rotation angle.
The tradeoff here is that too small an incremental rotation can be insignificant compared to statistical noise,
and too large an incremental rotation can lead to cumulative rotations that go too far and `turn the corner' — a
naive version of classical `buffer overflow' in a single qubit.
The incremental rotation angle was chosen to be $\pi/24$ (as in Figure <ref>) because this gave
accurate results on the development set. Larger datasets would obviously warrant smaller angles to avoid the overflow issues, and
this parameter tuning could easily be automated for a larger variational learning approach.
The number of words used is partly a tradeoff between space and accuracy. The largest system available to us
had 20 algorithm qubits [20],
and offline simulations showed that perfectly accurate results could be expected with at least 9 words. To build
a circuit like that of Figure <ref> with 9 words and 2 topics requires 20 qubits, so
by a convenient accident, this was just able to run comfortably on available quantum hardware, yielding 100% accuracy.

For the word embeddings classifier of Section <ref>, only one qubit per dimension was needed, and
results were experimentally found to be 90% accurate with just 8 embedding dimensions, thus requiring only 8 qubits to run.
When running the densely encoded version of the word embeddings classifier from Section <ref>, 100% accuracy was achieved using 16 embedding dimensions and only 4 qubits [24]. This model achieves perfect accuracy for the  set and in the fewest qubits of all the methods covered.

To draw deeper conclusions on scalability, Alexander and Widdows [24] tested the QSVM classifiers on a more complex dataset of IMDb movie reviews [29]. Actual reviews taken from the database incorporated varied word combinations and colloquial language,
similar to a realistic use case for quantum NLP. The average number of words in each review is between 228 and 229, and classification experiments were performed in batches of 50 documents: the the number of word tokens involved in each experiment was around 11000 (whereas the total size of
the  training and test set is 465 words).
The percentage of samples correctly classified peaked when using 4 qubits, where average accuracy was 57% with the  and 62% using the densely encoded feature map. The QSVM experiments were on par with classical SVM on average, and classified some sample batches with perfect accuracy. This, in contrast with the  results, suggests that good classification merits compatibility of the specific text sample with the feature map or overall method. Such compatibility is not yet predictable and requires further investigation to draw conclusions on the potential of quantum NLP classification on a large scale.

§.§ Language Caveats and Dependencies

As well as the simple data size and scaling questions, there are many other language details to be considered, including
“What does splitting into words mean precisely?” (tokenization) and “How do we declare that
two words are the same?” (canonicalization). These questions were sidestepped for now by using particularly simple
English phrases as the training and test data. However, it is still important to bear in mind that all the approaches
require classical preprocessing of various sorts, including basic whitespace-splitting and assigning tokens to
qubit indices in the word-based classifier, word vector embedding training for the inputs to the SVM classifier, to the
need for a full natural language parse tree in the  package.

Rather than claiming that the bags-of-words
classifier is `the best' because it reaches the highest accuracy completely on a quantum hardware, we believe these comparisons
highlight important tradeoffs to consider. With a much more sophisticated linguistic model and related requirements for preprocessing, Lorenz et al.
[28] were able to reach 87% accuracy with only 6 qubits — whereas with the same restriction (implemented by
reducing the number of words considered), the bag-of-words classifier accuracy was reduced to 83% in simulations.
Having a range of available approaches puts us in a position where tradeoffs between space requirements, system complexity,
and results accuracy can be considered in the light of what problems users are trying to solve. For example, the work by Alexander and Widdows [24] investigates solely the effects of decreasing space in the QSVM using a densely encoded feature map. Improved accuracy from 90% to 100% in fewer qubits on the  dataset, albeit promising, translated to an unrealistic tradeoff between space and accuracy on the IMDb set.

For the problem of correctly classifying general text data samples using quantum computation, properly reflecting the complexity of language in quantum representations is challenging. The accuracies from quantum circuits are dependent on the compatibility between the language dataset, type of classes (sentiment, topic etc.), extent of preprocessing and structure of the resulting quantum state. It should be noted that constructing quantum representations for language for any feature-based computation should be purposeful and case-specific, for more effective handling of language dependencies. In this way, the bag-of-words classifier is a more universal approach to handling arbitrary language and classes; it relies only on tokenization compared to abstract feature mappings and word embeddings used by the QSVM.

§ BIGRAM MODELLING AND QUANTUM PROBABILITY

While the ability to combine classifier weights and get good results is important, it is obvious and well-known
that bag-of-words models are a poor approximation for language. Historically, one of the next steps in statistical
language modelling was the modelling language based on short sequences of characters and words, used by mathematician Claude Shannon
to illustrate key behaviors including entropy in the foundation of information theory. Shannon used the
terms `first-order approximation' for a model that samples and generates words based purely on their frequencies, and `second-order approximation'
for a model that conditions this probability on the preceding word. (For example,  yellow is likely to come
before but not after submarine.) Today these are often called unigram and bigram models, and
in principle such a model extends to sequences of any length, leading to the long-established field of n-gram language modelling <cit.>.
Having built a quantum unigram model, extending this to bigram modelling is a natural next step.

Though still relatively simple, semantic modelling for two-word bigram combinations has real-world applications. For example,
in the hospitality domain, book room, arrange accommodation, reserve hotel, make reservation all imply
the same intent or goal, even though they do not share the same words and these words are often not synonyms in other contexts
— for example, book and make are not normally synonyms in English. Recognizing that these phrases mean
similar things when combined in this way is this important for intent recognition in customer service dialog systems.

In probabilistic terms, a unigram model can be used for language generation by sampling terms from the distribution
of words, in which case a bigram model works by sampling from the joint distribution of (ordered) word pairs.
This has an established parallel in quantum probability theory, described in detail by Bradley [32].
A joint distribution over the vector spaces $V$ and $W$
is represented in the tensor product space $V\ot W$, in which case the marginal distributions are represented by
partial traces defined by $\tr_W(v\ot w) = v\, \tr(w)$ and $\tr_V(v\otimes w) = w\, \tr(v).$
Bradley 32 uses this approach to represent formal concept lattices in vector spaces.
Formal concept analysis is a theory developed by Georg Cantor 33 in which objects are represented
by which attributes they possess, and concepts arise as closures of sets of objects and attributes that go together.

§.§ Modelling Steps

The distributional modelling process outlined by Bradley 32 uses the following steps,
which are written out fully in the example in Table <ref>.

* Write down the joint distribution matrix (`Initial Distribution'). In the example in Table <ref>,
this joint distribution is a subset of the Cartesian product $\mathsf{Colors}\times\mathsf{Fruit}$.

* Express this distribution as an element of the tensor product space $\mathsf{Colors}\ot\mathsf{Fruit}$
by flattening the distribution matrix into a long vector.

* Normalize this element to get a distribution state vector $\ket{\psi}$.

* Take the outer product $\ket{\psi}\bra{\psi}$ which gives the density matrix of the joint distribution.

* Take partial traces of this density matrix. Each partial trace reveals information about the distribution
of the respective ingredients — in particular, the diagonal elements represent the individual marginal probabilities,
and the off-diagonal elements represent information about correlations between items.

Steps for modelling the concepts “red apple”, “green apple”, “yellow banana”

In the worked example of Table <ref>, the key thing to note is the off-diagonal $\frac{1}{3}$ terms
that link the red and green concepts in the partial trace showing colors. This reflects the fact that back in the original
distribution, these are both colors of apple. Note that classical marginalization leaves such information behind — the
classical marginal distribution would just tell us that red, green, and yellow are equally likely.
This property has been noted by various authors, and was put to work in the work of Sordoni et al. [13]
for term-weighting in information retrieval. Those authors recognized that the weight given for a combination of words
should sometimes be different from the additive weights of the individual words — taking an example from earlier,
the weight of the term horse in the phrase “I love the flowers on horse chestnut trees” should be suppressed
because it is unlikely to be relevant for users whose search terms include horse on its own.

§.§ Quantum Circuit Approximation for Small Distribution

The initial quantum implementation goal was to build a joint bigram distribution in a way that can potentially
be used for language understanding and generation from a probabilistic model. One of the general challenges here is
that preparing a quantum state representing an arbitrary large state vector is difficult —
as discussed in Section <ref>, explicitly preparing and comparing vectors
dimensions requires procedures like the divide-and-conquer method developed by Araujo et al [34]. This worked
reasonably well for embedding 8 feature-dimensions in 3 qubits, but even with a small collection of words,
the corresponding model dimension is much larger, so instead of trying to create the state
$\braket{\psi}{\psi}$ from Table <ref> explicitly, we try to learn effective approximations.

For this demonstration, a slightly larger distribution of items and colors was used
including green apple, red apple, yellow banana, ripe banana, red pepper, yellow pepper, black shoes, red dress, blue suit, white shirt. This has 7 distinct prefixes and 7 distinct suffixes, so to model the joint distribution
in the manner of Table <ref> would require 49 dimensions and $49^2$ for the outer product density matrix.

Instead, in order to fit the distribution into quantum memory and to induce some interference between terms,
a dense encoding scheme was used.
We use a Quantum Circuit Born Machine (QCBM) model to learn the joint probability distribution. The QCBM encodes the probability of (prefix, suffix) pairs directly as the amplitudes of different states in the superposition. This way, the normalization is satisfied by default. For a joint distribution with $n$ prefixes and $m$ suffixes, we would need $nm$ classical bits just to model `present or absent'. For the QCBM model,
we use $\lceil\log_2(n)\rceil + \lceil\log_2(m)\rceil$ qubits, and an encoding convention where each prefix and suffix is given a binary index,
and the cooccurrence weight is stored as the amplitude of the state given by concatenating these two indices.
Each of the adjectives and nouns was assigned a binary
index corresponding to a tensor product state, for example $\textit{blue} = \ket{101}$ and $\textit{shoes} =\ket{100}$.
These are concatenated to form the bigram index, $\textit{blue shoes} = \ket{101100}$.

The QCBM uses parametric quantum circuits to generate different superpositions. The training challenge is then to find the proper set of parameters that lead to the generation of the specific superposition that represents the target joint probability distribution. For this, a
Simultaneous Perturbation Stochastic Approximation (SPSA) optimizer  [35] was implemented which optimizes the parametric quantum circuit, minimizing the difference between the generated distribution and the target distribution using the Kullback–Leibler (KL) divergence as the cost function. Sample results are shown in Figure <ref>.
The initial results were disappointing (middle column) — while finding some peaks in the distribution, the optimizer
entirely missed others, leading to a poor KL-divergence score of $1.131$. Our hypothesis was that the target distribution
was too discrete or `spiky' to be fitted effectively in this way.

Further experiments were carried out that added noise to the distribution and tried to fit the noisy version.
Perhaps surprisingly, this worked considerably better — the optimizer was able to fit most of the spikes in the distribution, at the cost
of giving some weight to other elements, achieving a much better KL-divergence of $0.211$.

Attempts to fit the target distribution, with and without introducing noise. The goodness-of-fit is measured by Kullback-Liebler (KL) divergence,
$D_\text{KL}(P \parallel Q) = \sum_{x\in\mathcal{X}} P(x) \log\left(\frac{P(x)}{Q(x)}\right)$, where $P$ is the learned distribution and $Q$ is the target distribution.

This result is analogous to the use of smoothing in $n$-gram models. It is often observed
that language produces new words and phrases that have not been seen before: this is what is meant when language is said to be
`generative'. To accommodate this, language models are adapted to give non-zero probabilities even to phrases that have never been encountered in training,
and there are several traditional ways of doing this <cit.>.
In a simple demonstration, after training, the model was used to generate a few new phrases by random sampling. Results included some plausible
example like black suit, and occasionally misfits such as ripe shirt.

§.§ Quantum Circuit Approximation for Larger Cue-Target Distributions

This section investigates how these quantum circuits and results behaved at a larger scale with more realistic data.
For this, a larger collection of pairs was needed, for which the University of South Florida Free Association Norms
dataset was used [36]. This dataset collects many results of experiments where subjects were
given a prompt-word, such as add, and responded with a word they consider associated,
such as subtract or calculate. This dataset has been used to compare different models for analyzing word-meaning
and retrieval [37], and to propose word-pairs for subsequent word-similarity ranking experiments [38]. After combining the input files, the word-graph used in our experiments had
1703 distinct cue words, 6359 distinct target words, and 24526 links from a cue to a target. Each link was weighted by the
forward-strength of the link as computed by Nelson et al 36.

Given $n=1703$ and $m=6359$, it would need $\lceil\log_2(n)\rceil + \lceil\log_2(m)\rceil = 24$ qubits to attempt to
model the whole graph distribution, which even with advances in recent months is beyond the current size of reliable
quantum computers [39]. This introduces the requirement of sampling from the larger graph to get representative subgraphs.
A natural problem here is that taking a random sample of nodes and retaining the edges between them does not preserve representative graph properties
— for example, if $p$ nodes are randomly sampled from a graph with $N$ nodes, the chance of a node $n$ being selected is $\frac{p}{N}$,
whereas the chance of an edge $(n_1, n_2)$ being selected is roughly $\frac{p}{N^2}$ because both $n_1$ and $n_2$ need to be selected.
Graph sampling challenges and example solutions are surveyed by Leskovec and Faloutsos 40: in these terms, the graph sampling challenge
would be described as a kind of scale-down sampling, and the method used is related to the random walk family. More precisely,
a subgraph is grown by starting with a small set of seed nodes, scoring their neighbors according to the sum of edge-weights
connecting them with the seed nodes, and adding batches of the $k$ neighbors with the best scores until the desired number of nodes is reached.
In our bipartite graph this process alternates between cues and targets, so the same number of each is sampled. An example subgraph
with 10 cues and 10 targets starting with the seed word acorn is shown in Figure <ref>.

Bipartite cue-target graph grown around the seed-word acorn

Nodes in Graph           16           32

Prec.     Rec.     F1    Prec.     Rec.     F1

SPSA              0.062     0.047     0.053     0.042     0.029     0.034

SPSA Smoothed     0.041     0.033     0.036     0.025     0.019     0.022

Shared Links      0.054     0.045     0.049     0.032     0.025     0.028

Random            0.046     0.034     0.039     0.040     0.029     0.033

Nodes in Graph           64           128

Prec.     Rec.     F1    Prec.     Rec.     F1

SPSA              0.022     0.016     0.019     0.011     0.008     0.009

SPSA Smoothed     0.015     0.011     0.013     0.008     0.006     0.006

Shared Links      0.051     0.039     0.044     0.056     0.041     0.048

Random            0.020     0.015     0.017     0.011     0.008     0.009

Precision, recall, and F1-score of link recovery experiments for graphs up to 128 nodes. Each
figure is the average of 100 experiments with graph grown around a randomly chosen seed word.

This technique was used to create a 100 sample subgraphs containing each of 16, 32, 64, 128 modes, by choosing
a random cue-word (sampling uniformly from all cues) and growing a subgraph around that word. The pattern of
being able to approximate target distributions more effectively with some smoothing was confirmed —
for example, the average KL-divergence between the learned and the target distributions with 16 nodes was
1.504 without smoothing and 0.454 with smoothing.

A further experiment was performed to see how these learned distributions perform at generating new links.
This was simulated by removing 20% of the links in the sampled subgraphs in a random train-test split, training
the models on the 80% of training links, taking the pairs with the highest probabilities in the learned distribution that
were not links in the training graph, and comparing these with the 20% of held-out test links.
The results were evaluated using the standard scores of precision (number of correct links divided by number of
proposed links), recall (number of correct links divided by number of test links that could be found), and F1-score
(the geometric mean of precision and recall) <cit.>. The results of this experiment are
shown in Table <ref>. In spite of the the better KL-divergence scores, the SPSA
results with smoothing are consistently less good than those without, and are sometimes worse than the random
baseline scores. For small graphs (16 and 32 nodes), the SPSA method performs better than randomly, and better than
an alternative Shared Links approach, which uses a similar link-scoring technique to that used for selecting the
sample subgraphs to rank the most promising available new links.
However, for the larger graphs (64 and 128 nodes), the Shared Links method pulls ahead.

These results are somewhat disappointing, though representative of some of the challenges quantum NLP
is likely to face. Mathematically exciting models may lead to promising implementations, from which we can
learn a lot about distributional patterns and propose improvements. However, classical computers can
still process much more data quickly so in many cases a relatively simple classical baseline
algorithm can still produce better results.

§ AMBIGUITY RESOLUTION IN COMPOSITION

The ability to choose appropriate interpretations for ambiguous words is a hallmark of human language capability.
Much of the time, we guess meanings quickly and correctly, but various experiments have also shown that in some
situations, several meanings are not only available but cognitively activated, causing and confusion and delay
in human language responses <cit.>.
[Sometimes ambiguity resolution is so effortless that we underestimate the prevalence of ambiguity itself,
which takes many forms. For example, English has considerable syntactic ambiguity — one large sample found that
57% of the 400 most common English verbs are also nouns [42], but we rarely notice this.
As noted by [43], “Nearly all
papers in formal semantics start from the assumption that all the words
in the examples under study have been neatly disambiguated before
being combined. But this is not an innocent or easy assumption.”]

Word-sense discrimination and disambiguation were among the early successes of word vector models during the 1990's,
built using dimension-reduction of term-document or term-term cooccurrence matrices [44]. This was
followed by the use of orthogonal projection as a logical operator for isolating particular senses of ambiguous
words, confirming that a semantic vector for an ambiguous word can be analyzed as a sum of
vectors for difference senses, which can sometimes be recovered from the geometry of the
vector space <cit.>.

The ambition of combining distributional word vectors with compositional operations that model grammatical structures
led to successful experiments with matrices as operators — for example, where nouns are modelled as vectors, adjectives
can be modelled more effectively as matrices acting upon the noun vectors [45]. Putting
such insights together enabled comprehensive systems for distributional compositional semantics to be devised
[46, 43], leading to many successful experiments
(for a more thorough summary see Widdows et al. [16]).

As noted by authors including Baroni and Zamparelli [45], the use of matrices to operate on vectors supports disambiguation
as different components of meaning are selected in the compositional process. For example, we might learn that red
means something closer to orange in `red hair', something closer to purple in `red wine', and something closer
to urgent in `red alert'.

A toy domain model with column vectors for nouns and matrices for transitive verbs

70 Borneo
70 Java
70 C++
70 Trip
70 Juggling

Place     1     1     0     0     0

Event     0     0     0     1     0

Tech     0     1     1     0     0

Skill     0     0     0     0     1

\sf{visit} =
\begin{bmatrix}
0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}

\sf{learn} =
\begin{bmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}

To demonstrate such a process on quantum computer, we designed the example domain shown in Table <ref>.
There are only four dimensions, representing the broad areas place, event, technology, skill, and 5 nouns — one belonging to
each dimension, and the noun Java which could refer to a place or a technology. Consider now the transitive verbs visit and learn.
When we say “I visited Borneo”, this indicates that an event happened — so the verb visit takes places as input and creates events as output.
When we say “I learned C++”, this indicates that a skill was acquired — so the verb learned in this case takes technologies as input
and creates skills as output. It is easy to write down matrices that perform these operations (Table <ref>, right hand side).

Consider now the action of these matrices on the ambiguous word Java. Both the place and the tech dimensions are activated
with this input, but the verb visit simply ignores the tech part of the input, whereas the verb learn ignores the place part.
In the process of composition, the meanings that naturally combine with one another are preserved, and those that do not are discarded.

Circuit for Java
Circuit for visit
Circuit for visit Java

Toy circuit examples showing how the phrase visit Java selects the place meaning

This process was then modelled using the quantum circuits in Figure <ref>. Qubits corresponding to the dimensions for Java are activated by applying the $X$ gate, and the verb visit is implemented
by connecting the input place qubit to the output event qubit. The quantum circuit is actually more complicated mathematically than
the small matrices of Table <ref> — for example, the state of the four input qubits would be represented in
$(\mathbb{C}^2)^{\ot 4}\cong \mathbb{C}^{16}$. These interactions would have to be considered when modelling a larger domain, if only
because the approach in Figure <ref> would soon run out of qubits. Nonetheless, an experiment with these circuits
on the 11-qubit IonQ machine gave the expected results — measuring the output bits for the visit Java or the corresponding learn Java
circuits shows that the former activates the event output and the latter activates the skill output. Ambiguity is an example
of a problem that is crucial to language understanding, to which the mathematical tools of vectors and matrices have been successfully applied,
and the circuits of Figure <ref> provide an example of how such processes can be implemented on quantum computers.

§ RELATED WORK

These experiments and results come in the midst of much progress in quantum machine learning and AI.
Until recently, most work in quantum algorithms was theoretical in how these algorithms
could not be run on quantum hardware. This has changed rapidly, and in the 2020's,
new results from quantum computers in artificial intelligence are being published almost every month,
with applications including probabilistic reasoning [47]
financial modeling [19], and image classification [48, 49].
Similar questions arise across these areas, partly because the availability of
some of the key quantum properties like indeterminacy, interference, and entanglement
pose the question “How can these mathematical properties help to model a given situation?”

The most directly comparable research to that presented here is the compositional quantum approach
released in the  package [50, 27]. This is the ongoing culmination of
a research program outlined by Coecke et al. 46, which is often referred to as the DisCoCat
(`distributional compositional categorical') model. This combines the use of distributional semantic vectors
with syntactic parsing, and partly follows the tradition of logical semantics in the sense that the semantic
representation is derived from first finding the syntactic or grammatical structure of a sentence.

Such an approach to meaning is common in theoretical linguistics, which often considers
sentences as fundamental units of language and require grammaticality. The relationship between
categorial grammar and compositional semantics especially is a key part of Montague grammar [51].
Such direct predecessors in NLP today are sometimes obscured by the tremendous success of
machine learning methods since the early 2000's: as the field has
coalesced around a few particularly successful techniques, other topics that would once have been
included in a standard introduction to language and meaning have become less well-known.
A renewed interest in logical semantics encouraged by its use in DisCoCat could bring insights
independently of its potential applications in quantum NLP.

At the same time, precedents in logical semantics also bring reservations — starkly, for example,
in 1976 philosopher David Lewis wrote,
“It is apparent that categorial grammars of this sort are not reasonable grammars for natural language”
[52]. Lewis' concerns were partly about the inability of phrase-structure grammars to
account for freer word-orders, which motivates the addition of a transformational component. This helps to
adapt the machinery to grammatical structures in more languages, but maintains the assumption that systems
are working with grammatical sentences to begin with.
While this is still appropriate in many formal domains, the pervasive availability this century
of mobile electronic devices has led to a deluge of informal text which also (and frequently!)
demands our attention.

The challenge of inferring grammatical structure from informal text could itself become an opportunity
for QNLP, since early studies suggest that language parsing can be done efficiently on quantum computers [53]. This raises the possibility that grammatical structure could interact with
the semantic compositional structure in a model such as DisCoCat as quantum information, rather than
as a fixed piece of classical information from a preprocessing step, which could make the system
more efficient and effective when working with incomplete or indeterminate parses.

An approach
based more on information retrieval 11, 12
starts bottom-up with individual words instead of grammatical sentences, and moves from there to pairs of words [13].
The examples in this paper have more obviously drawn on this research, partly because we believe it
will be applicable to more language situations in general.
Another family of
techniques that combines syntax and semantics has been to train deep neural networks
and distill both semantic and grammatical information together from these [54].
The use of tensor product decomposition networks has particularly interesting overlaps with models
used in quantum chemistry [55].

However, the most advanced language systems
in widespread use currently are neural networks such as GPT-3 that do not use explicit grammatical preprocessing
at all,
and these models are so fluent that critiques of them focus on semantic and ethical failures instead
of anything related to grammar and syntax [56].
Human grammatical fluency is still scientifically interesting, but the lack of it is no longer a weak-link
in language processing systems: language generation systems can easily produce
“massive amounts of very plausible but often untrue texts” [57]. For this reason we
expect aligning semantics and factual accuracy to be a more pressing engineering challenge
than aligning semantics and syntax.

Given the huge range of language challenges in computing, and pace of development
in both language processing and quantum computing, we expect
that the next few years will witness many more contributions and combinations.

§ CONCLUSIONS AND NEXT STEPS

The experiments and demonstrations presented in this paper show that NLP tasks can be performed on
quantum computers, which is important in itself — quantum information processing is being demonstrated on
quantum hardware, not just in theory. The practical applications are so far small-scale, and it is still challenging to
find consumer-facing NLP requirement that would be better served today by quantum than classical hardware.
And as demonstrated in some of our experiments, a more elegant mathematical method may produce worse results
than a simple baseline model that can train on more realistic data.

The main dependency here is hardware: because quantum memory capacity grows exponentially with the number of qubits,
10 qubits can represent a kilobyte, whereas 30 qubits can represent a gigabyte (roughly speaking — this compares
the number of variables, not their expressivity or access patterns, and classical memory is still much more reliable).
This threshold is likely to be crossed in the next two years, which will enable us to
explore larger datasets, and to look for useful intermediate-scale applications.

The scaling challenge is particularly important in NLP, because one of the consistent findings in this paper
is that promising results with very small curated datasets do not always translate into good performance on larger,
more varied and realistic datasets. This challenge is analyzed in detail by Alexander and Widdows 24,
where it shown that the that enough data can be processed to get results that are reliably above baseline
in a statistical sense, but still much less than is regularly used in classical NLP systems.

Though much of the focus in NLP research in recent years has been on larger and larger models, many
commercial systems involve much smaller curated datasets, such as the intents used by dialog systems
or ticket classifications used by customer service tracking systems. With a dedicated focus on building useful products,
it should become possible for quantum NLP to help with practical medium-term goals, and this can help show the
way to more general intelligent systems.

§ DATA AVALIABILITY

The datasets that were analyzed in the current study may be found at the following public domain resources:

* Lambeq: CQCL Github repository at <https://github.com/CQCL/lambeq>

* IMDb: <https://ai.stanford.edu/ amaas/data/sentiment/>

* University of South Florida Free Association Norms: Available through the supplementary material at <https://doi.org/10.3758/BF03195588>

Conflict of Interest: The authors declare that they have no conflict of interest.

#1ISBN #1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1<https://doi.org/#1>et al.#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1<><#>1#1#1#1#1#1#1#1#1#1#1#1#1#1PreBibitemsHook

[1]

Widdows, D.:
A mathematical model for context and word-meaning.
In: International and Interdisciplinary Conference on Modeling and
Using Context,
pp. 369–382

[2]

Dirac, P.:
The Principles of Quantum Mechanics,
4th edition, 1958, reprinted 1982 edn.
Clarendon Press,

[3]

Orrell, D.:
Quantum Economics and Finance: An Applied Mathematics Introduction.
Panda Ohana Publishing,
New York

[4]

Busemeyer, J.R.,
Bruza, P.D.:
Quantum Models of Cognition and Decision.
Cambridge University Press,

[5]

Schrödinger, E.:
Discussion of probability relations between separated systems.
In: Mathematical Proceedings of the Cambridge Philosophical Society,
vol. 31,
pp. 555–563
Cambridge University Press

[6]

Cooke, H.P.,
Treddenick, H. (eds.):
Aristotle: Categories, On Interpretation, Prior Analytics.
Loeb Classical Library.
Harvard University Press,

[7]

Piedeleu, R.,
Kartsaklis, D.,
Coecke, B.,
Sadrzadeh, M.:
Open system categorical quantum semantics in natural language processing.
arXiv preprint arXiv:1502.00831

[8]

Coecke, B.,
de Felice, G.,
Meichanetzidis, K.,
Toumi, A.:
Foundations for near-term quantum natural language processing.
arXiv preprint arXiv:2012.03755

[9]

Géron, A.:
Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow:
Concepts, Tools, and Techniques to Build Intelligent Systems.
O'Reilly Media,

[10]

Nielsen, M.A.,
Chuang, I.:
Quantum Computation and Quantum Information.
American Association of Physics Teachers,
Cambridge University Press Edition, 2016

[11]

Van Rijsbergen, C.J.:
The Geometry of Information Retrieval.
Cambridge University Press,

[12]

Widdows, D.:
Geometry and Meaning.
CSLI Publications,

[13]

Sordoni, A.,
Nie, J.-Y.,
Bengio, Y.:
Modeling Term Dependencies with Quantum Language Models for
In: Proceedings of the 36th International ACM SIGIR Conference
on Research and Development in Information Retrieval.
SIGIR '13,
pp. 653–662

[14]

Cohen, T.,
Widdows, D.,
Vine, L.D.,
Schvaneveldt, R.,
Rindflesch, T.C.:
Many paths lead to discovery: Analogical retrieval of cancer
In: Sixth International Symposium on Quantum Interaction

[15]

Birkhoff, G.,
von Neumann, J.:
The logic of quantum mechanics.
Annals of Mathematics

[16]

Widdows, D.,
Kitto, K.,
Cohen, T.:
Quantum mathematics in artificial intelligence.
Journal of Artificial Intelligence Research

[17]

Orrell, D.,
Houshmand, M.:
Quantum propensity in economics.
Frontiers in Artificial Intelligence

[18]

Pothos, E.M.,
Busemeyer, J.R.:
Quantum cognition.
Annual review of psychology

[19]

Johri, S.,
Debnath, S.,
Mocherla, A.,
Singk, A.,
Prakash, A.,
Kim, J.,
Kerenidis, I.:
Nearest centroid classification on a trapped ion quantum computer.
npj Quantum Information

[20]

IonQ Aria:
IonQ Aria Furthers Lead As World’s Most Powerful Quantum Computer.
accessed 2022-05-28

[21]

ANIS, M.S.,
Abraham, H.,
Agarwal, R.,
Agliardi, G.,
other authors:
Qiskit: An Open-source Framework for Quantum Computing

[22]

Kowsari, K.,
Jafari Meimandi, K.,
Heidarysafa, M.,
Mendu, S.,
Barnes, L.,
Brown, D.:
Text classification algorithms: A survey.

[23]

Widdows, D.:
Nonlinear addition of qubit states using entangled quaternionic powers of
single-qubit gates.
arXiv preprint arXiv:2204.13787

[24]

Alexander, A.,
Widdows, D.:
Quantum text encoding for classification tasks.
In: 2022 IEEE/ACM 7th Symposium on Edge Computing,
pp. 355–361

[25]

Mikolov, T.,
Chen, K.,
Corrado, G.,
Dean, J.:
Efficient estimation of word representations in vector space.
arXiv preprint arXiv:1301.3781

[26]

Havlicek, V.,
Corcoles, A.,
Temme, K.,
other authors.:
Supervised learning with quantum-enhanced feature spaces.

[27]

Kartsaklis, D.,
Fan, I.,
Yeung, R.,
Pearson, A.,
Lorenz, R.,
Toumi, A.,
de Felice, G.,
Meichanetzidis, K.,
Clark, S.,
Coecke, B.:
lambeq: An Efficient High-Level Python Library for Quantum NLP.
arXiv preprint arXiv:2110.04236

[28]

Lorenz, R.,
Pearson, A.,
Meichanetzidis, K.,
Kartsaklis, D.,
Coecke, B.:
QNLP in practice: Running compositional models of meaning on a quantum
arXiv preprint arXiv:2102.12846

[29]

Maas, A.L.,
Daly, R.E.,
Pham, P.T.,
Huang, D.,
Ng, A.Y.,
Potts, C.:
Learning word vectors for sentiment analysis.
In: Proceedings of the 49th Annual Meeting of the Association for
Computational Linguistics,
pp. 142–150.
Portland, Oregon, USA

[30]

Shannon, C.:
A mathematical theory of communication.
Bell system technical journal

[31]

Manning, C.D.,
Schütze, H.:
Foundations of Statistical Natural Language Processing.
The MIT Press,
Cambridge, Massachusetts

[32]

Bradley, T.-D.:
At the interface of algebra and statistics.
PhD thesis,
City University of New York

[33]

Ganter, B.,
Wille, R.:
Formal Concept Analysis: Mathematical Foundations.
Springer, ???

[34]

Araujo, I.F.,
Park, D.K.,
Petruccione, F.,
da Silva, A.J.:
A divide-and-conquer algorithm for quantum state preparation.
Nature Scientific Reports

[35]

Spall, J.C.:
An overview of the simultaneous perturbation method for efficient
Johns Hopkins apl technical digest

[36]

Nelson, D.L.,
McEvoy, C.L.,
Schreiber, T.A.:
The University of South Florida free association, rhyme, and word
fragment norms.
Behavior Research Methods, Instruments, & Computers

[37]

Bruza, P.,
Kitto, K.,
Nelson, D.,
McEvoy, C.:
Is there something quantum-like about the human mental lexicon?
Journal of mathematical psychology

[38]

Chandrasekaran, D.,
Mago, V.:
Evolution of semantic similarity — a survey.
ACM Computing Surveys (CSUR)

[39]

IonQ Benchmarking:
Algorithmic Qubits: A Better Single-Number Metric.
<https://ionq.com/posts/february-23-2022-algorithmic-qubits>, accessed

[40]

Leskovec, J.,
Faloutsos, C.:
Sampling from large graphs.
In: Proceedings of the 12th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining,
pp. 631–636

[41]

Aitchison, J.:
Words in the Mind: An Introduction to the Mental Lexicon,
3rd edn.

[42]

Widdows, D.:
Unsupervised methods for developing taxonomies by combining syntactic
and statistical information.
In: Proceedings of North American Chapter of the Association for
Computational Linguistics,
Edmonton, Canada

[43]

Baroni, M.,
Bernardi, R.,
Zamparelli, R., :
Frege in space: A program for compositional distributional semantics.
Linguistic Issues in language technology

[44]

Schütze, H.:
Automatic word sense discrimination.
Computational Linguistics

[45]

Baroni, M.,
Zamparelli, R.:
Nouns are vectors, adjectives are matrices: Representing
adjective-noun constructions in semantic space.
In: Proceedings of the 2010 Conference on Empirical Methods in Natural
Language Processing (EMNLP)

[46]

Coecke, B.,
Sadrzadeh, M.,
Clark, S.:
Mathematical foundations for a compositional distributional model of meaning.
CoRR, arXiv preprint arXiV:1003.4394

[47]

Borujeni, S.E.,
Nannapaneni, S.,
Nguyen, N.H.,
Behrman, E.C.,
Steck, J.E.:
Quantum circuit representation of Bayesian networks.
Expert Systems with Applications

[48]

Wang, K.,
Xiao, L.,
Yi, W.,
Ran, S.-J.,
Xue, P.:
Experimental realization of a quantum image classifier via
tensor-network-based machine learning.
Photonics Research

[49]

Johri, S.,
Zhu, E.,
Bacon, D.,
Esencan, M.,
Kim, J.,
Muir, M.,
Murgai, N.,
Nguyen, J.,
Pisenti, N.,
Schouela, A., et al.:
Generative quantum learning of joint probability distribution functions.
Bulletin of the American Physical Society

[50]

Coecke, B.,
de Felice, G.,
Meichanetzidis, K.,
Toumi, A.:
Quantum Natural Language Processing: “We did it! On an actual quantum

[51]

Partee, B.H.:
Montague Grammar.
Academic Press, Inc.,

[52]

Lewis, D.:
General semantics.
In: Montague Grammar,
pp. 1–50.
Academic Press, Inc.,

[53]

Wiebe, N.,
Bocharov, A.,
Smolensky, P.,
Troyer, M.,
Svore, K.M.:
Quantum language processing.
arXiv preprint

[54]

Palangi, H.,
Huang, Q.,
Smolensky, P.,
He, X.,
Deng, L.:
Grammatically-interpretable learned representations in deep NLP
In: Advances in Neural Information Processing Systems Workshop

[55]

McCoy, R.T.,
Linzen, T.,
Dunbar, E.,
Smolensky, P.:
Tensor product decomposition networks: Uncovering representations of
structure learned by neural networks.
Proceedings of the Society for Computation in Linguistics

[56]

Floridi, L.,
Chiriatti, M.:
Gpt-3: Its nature, scope, limits, and consequences.
Minds and Machines

[57]

Sobieszek, A.,
Price, T.:
Playing games with ais: The limits of gpt-3 and similar large language
Minds and Machines