Also at ]Center for Complex Systems Studies, Utrecht University. Also at
]Center for Complex Systems Studies, Utrecht University.

Also at ]Center for Complex Systems Studies, Utrecht University

# Grover’s Algorithm for Question Answering

A. D. Correia<EMAIL_ADDRESS>[  H. T. C. Stoof  [  Institute for
Theoretical Physics, Utrecht University
Princetonplein 5, 3584 CC Utrecht, The Netherlands  M. Moortgat  [  Utrecht
Institute of Linguistics OTS, Utrecht University
Trans 10, 3512 JK Utrecht, The Netherlands

###### Abstract

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

††preprint: APS/123-QED

##  I Introduction

Recent developments in quantum computation have given rise to new and exciting
applications in the field of Natural Language Processing (NLP). Pioneering
work in this area is the DisCoCat framework [1, 2], which introduces a
compositional mapping between types and derivations of Lambek’s typelogical
grammars [3, 4] and a distributional semantics [5] based on vector spaces,
linear maps and tensor products. This allows for the representations of words
as multi-partite quantum states, predicting that, when contracted with one
another, the meaning of larger text fragments is encoded in the resulting
quantum states. A number of theoretical advances have followed, for instance
in expanding the toolbox of word representations with density matrices [6], so
as to achieve good results on discerning different word and phrase senses [7,
8, 9]. Subsequent work has shown how to entertain simultaneously different
possible interpretations of texts, either by looking at an incremental
interpretation of the parsing process [10], or by considering a single
representation for the multiple readings of syntactic ambiguities [11, 12].

The challenge now is to implement these contractions in quantum circuits. To
this end DisCoCirc [13] introduces a different way of representing the meaning
of a sentence, where certain words are seen as quantum gates that act as
operators on input states representing other words. The DisCoCirc approach
uses quantum machine learning algorithms [14] for NLP [15, 16] where circuit
parameters, related to word representations, are then learned by classical
optimization and used to predict different binary labels statistically, such
as the answers to yes-no questions [17], topics of phrases, or the distinction
between subject and object relative clauses [18].

Although these implementations can play an important role in speeding up NLP
tasks based on current machine-learning ideas and techniques, they do not go
beyond the current paradigm in terms of task evaluations. Importantly, the
previous results obtained using the DisCoCat tensor contractions cannot be
directly reproduced, since the mapping from a phrase to a circuit requires
extra steps that deviate from the original grammatical foundation, not
treating every word as an input at the same level. This presents a strong
incentive to find an alternative quantum-circuit implementation that sticks to
the original grammatical formulation, preserving the previous achievements,
where all words are taken as input on an equal footing. In addition, it is our
belief that a quantum framework can contribute a great deal to the
reestablishment of rule-based NLP, as a desirable alternative to large-scale
statistical approaches [19], since certain computations become more efficient
if we use the appropriate quantum algorithms, as we will illustrate in the
case of question-answering where quadratic quantum speedup can be achieved.

The paper is structured as follows. In Sec. II we develop the grammatical
framework and quantum state interpretation thereof, setting the stage for the
types of linguistic problems we will deal with here. In Sec. III we put
forward an approach where the contractions between word representations are
implemented as the measurement of a permutation operator, and we show how this
permits the simultaneous treatment of ambiguous phrases in English. In Sec. IV
we apply Grover’s algorithm to question-answering, using the framework
developed in the previous section to turn the representation of the question
and answers into the input of the algorithm, together with an oracle that
identifies that correct answers. Finally, in Sec. V we give an overview of the
developments introduced and discuss further work.

##  II Syntax-semantics interface

In this section we introduce the grammatical framework that we will be working
with. It consists of a categorial grammar as the syntactic front end, together
with a compositional mapping that sends the types and derivations of the
syntax to a vector-based distributional interpretation. This is necessary to
understand the type of linguistic problems that we can address and how they
can be solved using a quantum circuit.

###  II.1 Type logic as syntax

The key idea of categorial grammar formalisms is to replace the parts of
speech of traditional grammars (nouns, adjectives, (in)transitive verbs, etc)
by logical formulas or types; a deductive system for these type formulas then
determines their valid combinations. The idea can be traced back to
Ajdukiewicz [20], but Lambek’s Syntactic Calculus [3] is the first full-
fledged formulation of a categorial type logic that provides an algorithm to
effectively decide whether a phrase is syntactically well formed or not.

Let us briefly discuss types and their combinatorics. We start from a small
set of primitive types, for example $s$ for declarative sentences, $n$ for
noun phrases, $w$ for open-ended interrogative sentences, etc. From these
primitive types, compound types are then built with the aid of three
operations: multiplication $\bullet$, left division $\backslash$ and right
division $/$. Intuitively, a type $A\bullet B$ stands for the concatenation of
a phrase of type $A$ and a phrase of type $B$ (“$A$ and then $B$”).
Concatenation is not commutative (“$A$ and then $B$” $\neq$ “$B$ and then
$A$”). Hence we have left vs right division matching the multiplication:
$A\backslash B$ can be read as “give me a phrase $A$ to the left, and I’ll
return a phrase $B$”; $B/A$ is to be interpreted as “give me a phrase $A$ to
the right, and I’ll return a phrase $B$”. We can codify this informal
interpretation in the rules below, where $A_{1}\bullet\cdots\bullet
A_{n}\vdash B$ means that from the concatenation of phrases of type
$A_{1},\ldots,A_{n}$ one can derive a phrase of type $B$. Hence,

$\displaystyle B/A\bullet A\vdash B,$ (1) $\displaystyle A\bullet A\backslash
B\vdash B.$ (2)

As examples of simple declarative sentences, consider _Alice talks_ , or _Bob
listens_. In the former case, we assign the type $n$ to _Alice_ and the type
$n\backslash s$ to the intransitive verb _talks_. We start by multiplying the
word types in the order by which the words appear, forming $n\bullet
n\backslash s$. Then, it suffices to apply rule (2), with $A=n$ and $B=s$, to
show that $n\bullet n\backslash s$ derives $s$, i.e. constitutes a well-formed
sentence. Conversely, the lack of a derivation of $s$ from $n\backslash
s\bullet n$ (_talks Alice_) allows us to conclude that this not a well-formed
sentence. These, and the later examples, illustrate only the simplest ways of
combining types, but these will suffice for the purposes of this paper. To
obtain a deductive system that is sound and complete with respect to the
intended interpretation of the type-forming operations, Lambek’s Syntactic
Calculus also includes rules that allow one to infer $A\vdash C/B$ and
$B\vdash A\backslash C$ from $A\bullet B\vdash C$. Moreover, to deal with
linguistic phenomena that go beyond simple concatenation, Lambek’s type logic
has been extended in a number of ways that keep the basic mathematical
structure intact but provide extra type-forming operations for a finer control
over the process of grammatical composition. See Ref. [21] for a survey, and
Ref. [12] for a quantum interpretation of such structural control operations.

####  II.1.1 Syntactic ambiguities

To see rule (1) in action, consider adjectives in English. An adjective is
expecting a noun to its right, and, once it is composed with a noun, it must
derive something that can be used, for instance, as the argument of an
intransitive verb, which, as we have seen, is of type $n$. Thus, an adjective
must be of type $n/n$, and we can use rule (1) to prove that, as an example,
rigorous mathematicians is a well-formed phrase of type $n$.

For certain phrases, there is more than one way of deriving the target type,
with each derivation corresponding to a distinct interpretation. As an
example, consider the noun phrase rigorous mathematicians and physicists, an
ambiguous structure that has already been studied in the context of vector
representations in Ref. [11]. Here the conjunction and gets the type
$(n\backslash n)/n$; for the complete phrase, we want to show that the
following judgement holds:

$n/n\bullet n\bullet(n\backslash n)/n\bullet n\vdash n.$ (3)

There are two possible interpretations: a first one, where the adjective
rigorous has scope over mathematicians and physicists, and a second one, where
it only has scope over mathematicians. Each of these interpretations is
connected to a different way of deriving the goal formula $n$. The first
reading is obtained by applying the rules in the following order

$\underbrace{n/n\bullet\underbrace{n\bullet\underbrace{(n\backslash
n)/n\bullet n}_{\text{(\ref{contright}) }\vdash n\backslash
n}}_{\text{(\ref{contleft}) }\vdash n}}_{\text{(\ref{contright}) }\vdash n},$
(4)

while for the second reading the rules apply in a different order as

$\underbrace{\underbrace{n/n\bullet n}_{\text{(\ref{contright}) }\vdash
n}\bullet\underbrace{(n\backslash n)/n\bullet n}_{\text{(\ref{contright})
}\vdash n\backslash n}}_{\text{(\ref{contleft}) }\vdash n}.$ (5)

Our goal is to treat both readings simultaneously until further information
allows us to clarify which of the readings is the intended one.

####  II.1.2 Question/answering

Question/answering (Q$\&$A) is one of the most common tasks in NLP [22].
Questions can be close ended, having “yes” or “no” for an answer, or open
ended, starting by “who”, “why” or “what”, also referred to as wh-questions.
For $P$ possible answers, it is always possible to turn wh-questions into
close-ended questions. If we know that either Alice, Bob, Carol or Dave is
talking, we can turn “Who talks?” into a series of four questions “Does [name]
talk?”. Thus, for $P$ possible answers, there are $P$ closed-ended questions
that we need to check 111This is a common way of turning Q$\&$A into a
classification problem, where each close-ended question gets a binary label,
depending on whether the answer is true or false. Binary classification
problems are some of the most well established applications of machine
learning. After finding a way of representing the question statements, usually
as single vectors, a number of these labeled statements is used to predict the
labels of the hold-out statements.. We would like to find the answer to the
open-ended questions directly, without this mapping. Syntactically, wh-
questions are open-endend interrogative sentences, and as such are assigned
their own type $w$. For a subject question, the type of the word who is thus
$w/(n\backslash s)$, since, when applied to an intransitive verb using rule
(2), it derives the interrogative type $w$.

###  II.2 Vectors as semantics

In the context of automatic processing of text, the most widely used form of
representing a word is by a unique array of values, referred to as a “word
embedding”. Seen as vectors, we can cluster or compare them using varied
geometric tools [24, 25, 26]. Representing the meanings of words as such is
widely known as “distributional semantics” [27]. In earlier work, vector
entries were related with how often a word would appear next to other words
[28], following the “distributional hypothesis” that states that words that
appear in similar contexts are themselves similar [29]. Nowadays, word
embeddings are extracted using language models, targeted on the prediction of
the most likely next word [30, 31]. This presents a problem for the
representation of larger fragments, since they are less likely to appear in a
text, making their distributional array rather sparse and thus not
particularly meaningful. Larger fragments can nevertheless receive an
embedding, but a direct connection with grammatical composition is lost.

To tackle this problem, the authors in Ref. [1] propose that the arrays
representing different words depend on their syntactic types, namely having a
dimensionality that mirrors their type complexity. This introduces a way of
composing the meanings of the individual words that is homomorphic to the
syntactic derivations, generating a representation of larger fragments from
the representation of smaller ones. For completeness, the mapping between the
syntax and the semantics is done using the formalism of vector spaces. Each
syntactic type $A$ is mapped to its semantic type via $\lceil A\rceil$. Each
semantic type is then interpreted as a vector space, where the particular
words are represented. Let there be three basic semantic spaces $\\{S,N,I\\}$.
The simple syntactic types $n$ and $s$ are mapped respectively to $\lceil
n\rceil=N$ and $\lceil s\rceil=S$. Each individual word is an element of the
semantic space that interprets its syntactic type. For instance, the
interpretation of the word physicists is now seen as a vector in $N$, this
being the vector space where the distributional information of nouns is
stored. Similarly, Alice talks is represented by a vector in $S$, that has as
basis elements two orthogonal states corresponding to “true” and “false”. The
interrogative type $w$ is mapped to $\lceil w\rceil=I\otimes N\otimes I\otimes
S$. The vector space $I$ (“index”) has basis elements that are in one-to-one
correspondence to the nouns that can be used as answers to the interrogative
sentence, providing an enumeration of the noun vectors of $N$. This will be
useful later when we need to index the quantum states associated with each
possible answer.

The vector spaces that translate the directional and multiplicative types are
obtained recursively as

$\displaystyle\lceil A\backslash B\rceil=\lceil A/B\rceil=\lceil A\bullet
B\rceil=\lceil A\rceil\otimes\lceil B\rceil,$ (6)

where $\otimes$ forms a tensor product space, inductively starting from
$A,B,C\in\\{n,s,w\\}$. Note that the tensor is commutative, such that $\lceil
A\rceil\otimes\lceil B\rceil\cong\lceil B\rceil\otimes\lceil A\rceil$. We
perform tensor contractions as the interpretations of the rules in Eqs. (1)
and (2). Thus, an intransitive verb is represented as a matrix in $N\otimes
S$, that when acting on a vector of type $N$ returns a vector in $S$. Using
the notation $\llbracket.\rrbracket$ to represent the tensor interpretation of
a word, and assuming an orthogonal basis $\\{\hat{n}_{i}\\}$ of $N$ and an
orthogonal basis $\\{\hat{s}_{i}\\}$ of $S$, the composition of the vectorial
interpretations of Alice and talks leads to the interpretation of the entire
sentence as a vector in $S$. The word meanings for this sentence are
represented as

$\displaystyle\llbracket\text{Alice}\rrbracket=\sum_{p}A_{p}\;\hat{n}_{p}$ (7)
$\displaystyle\llbracket\text{talks}\rrbracket=\sum_{qr}t_{qr}\;\hat{n}_{q}\otimes\hat{s}_{r},$
(8)

and the full sentence meaning as

$\displaystyle\llbracket\text{Alice
talks}\rrbracket=\llbracket\text{Alice}\rrbracket\cdot\llbracket\text{talks}\rrbracket=\sum_{pr}A_{p}t_{pr}\hat{s}_{r}.$
(9)

A more refined treatment of the translation from the Lambek types to tensor
spaces has been given in Ref. [11].

Similarly, the semantic space for an adjective can be seen as a matrix in
$N\otimes N$. Note that here the analogy between a matrix modifying a vector
and the adjective as a noun modifier is the clearest. Let us look at the
meanings of rigorous and mathematicians, which can be represented as

$\displaystyle\llbracket\text{rigorous}\rrbracket=\sum_{ij}r_{ij}\;\hat{n}_{i}\otimes\hat{n}_{j}$
(10)
$\displaystyle\llbracket\text{mathematicians}\rrbracket=\sum_{k}m_{k}\;\hat{n}_{k}.$
(11)

The meaning of rigorous mathematicians will be given by the application of the
translation of rule (1) to tensors. At the components level, it is the matrix
multiplication between the rigorous matrix and the mathematicians vector,
which gives, consistently with $n$ being the syntactic type of this fragment,
a vector in $N$, as

$\displaystyle\llbracket\text{rigorous}\;\text{mathematicians}\rrbracket$
$\displaystyle=\llbracket\text{rigorous}\rrbracket.\llbracket\text{mathematicians}\rrbracket$
$\displaystyle=\sum_{ij}r_{ij}\,m_{j}\;\hat{n}_{i}.$

The different order of application of Lambek rules in Eqs. (4) and (5)
translates into different vectors that represent the two readings of rigorous
mathematicians and physicists. The words and and physicists are given the
vector representations

$\displaystyle\llbracket\text{and}\rrbracket=\sum_{lmn}a_{lmn}\;\hat{n}_{l}\otimes\hat{n}_{m}\otimes\hat{n}_{n},$
(12)
$\displaystyle\llbracket\text{physicists}\rrbracket=\sum_{o}p_{o}\;\hat{n}_{o}.$
(13)

The reading from Eq. (4) is represented by the vector

$\displaystyle\llbracket\text{rigorous mathematicians and
physicists}\rrbracket_{1}$
$\displaystyle=\sum_{i}\,r_{ij}\,m_{l}\,a_{ljn}\,p_{n}\;\hat{n}_{i},$ (14)

whereas the reading from Eq. (5) is encoded in the vector

$\displaystyle\llbracket\text{rigorous mathematicians and
physicists}\rrbracket_{2}$
$\displaystyle=\sum_{m}\,r_{lj}\,m_{j}\,a_{lmn}\,p_{n}\;\hat{n}_{m}.$ (15)

For interrogative sentences, the word who will have the semantic function of
“lifting” an intransitive verb with representation in space $N\otimes S$ to a
representation in $I\otimes N\otimes I\otimes S$, since

$\displaystyle\lceil w/(n\backslash s)\rceil=I\otimes N\otimes I\otimes
S\otimes N\otimes S$ $\displaystyle\cong I\otimes N\otimes I\otimes S\otimes
S\otimes N.$ (16)

An element of this space contracts with an element of the representation space
of intransitive verbs, $N\otimes S$, associating the index of every possible
answer, in $I$, with both its representation in $N$ and its truth value in
$S$.

##  III Implementation

In this section we motivate a passage from vectors to quantum states and we
introduce them as inputs of quantum circuits that calculate contractions
between word representations.

###  III.1 Quantum states as inputs of a quantum circuit

To interpret text fragments taking into account their grammatical features
while staying in the vector framework, the dimension of the representation
quickly scales up with the complexity of the syntactic type, which has been a
limiting feature in distributional semantics implementations [32]. This
motivates a representation of words as quantum states, counting on the
potential of quantum computers to outperform the limitations of classical
computation both in terms of memory use [33] and in processing efficiency
[34].

Let us switch to a representation of word embeddings as vectors in complex-
valued inner product vector spaces, i.e. Hilbert spaces. Our atomic semantic
spaces $N$, $S$ and $I$ will now be replaced by their quantum counterparts as
the interpretation spaces. We thus have the Hilbert spaces $\mathcal{H}^{N}$,
$\mathcal{H}^{S}$ and $\mathcal{H}^{\otimes p}$ respectively, with
$\mathcal{H}^{\otimes p}$ the $p$-qubit Hilbert space corresponding to the
complex-valued realization of the semantic type $I$, where we assume that
$P=2^{p}$. For instance, with $\\{\ket{n_{i}}\\}$ the basis of
$\mathcal{H}^{N}$, we now have

$\llbracket\text{Alice}\rrbracket=\ket{\text{Alice}}=\sum_{p}A_{p}\;\ket{n_{p}}.$
(17)

Note that this space allows us to expand our representations with complex-
valued entries, and a proper contraction between the words will require the
conjugation of some of the components, i.e.

$\llbracket\text{Alice}\rrbracket^{*}=\bra{\text{Alice}}=\sum_{p}A^{*}_{p}\;\bra{n_{p}}.$
(18)

Let the input of a circuit be the product of the states that interpret each
word in the language fragment in question. Our running example of a noun
subject and an intransitive verb Alice talks is now represented as the input

$\ket{\text{Alice}}\ket{\text{talks}}\in\mathcal{H}^{N}\otimes\mathcal{H}^{N}\otimes\mathcal{H}^{S}.$
(19)

The basis of $\mathcal{H}^{S}$, $\\{\ket{s_{i}}\\}$, are the single-qubit spin
states $\ket{0}$ and $\ket{1}$, where the former represents a sentence that is
false, and the later one that is true. In this setting, it is also possible to
establish a probability distribution over the truthfullness of a sentence.

Each of the elements of the interpreting spaces will be represented by a
labeled quantum wire, thus rewriting the input state as

$\ket{\text{Alice}}\ket{\text{talks}}\in\mathcal{H}_{N}^{1}\otimes\mathcal{H}_{N}^{2}\otimes\mathcal{H}_{S}^{3},$
(20)

used as the input of a quantum circuit, as shown in Fig. 1.

$\Qcircuit@C=1em@R=2em@!R{&\lstick{\ket{\text{Alice}}\;1}\qw\qw\\\
\lstick{2}\qw\qw\\\
\lstick{3}\qw\qw\inputgroupv{2}{3}{1.2em}{1em}{\ket{\text{talks}}\qquad}}.$
Figure 1: Quantum circuit with intransitive sentence input.

The ambiguous fragment rigorous mathematicians and physicists will be
initially represented as a unique state in the tensor space, formed by
numbered copies of the $\mathcal{H}^{N}$ space as

$\displaystyle\ket{\text{rigorous}}\ket{\text{physicists}}\ket{\text{and}}\ket{\text{mathematicians}}$
(21)
$\displaystyle\in\mathcal{H}^{N}_{1}\otimes\mathcal{H}^{N}_{2}\otimes\mathcal{H}^{N}_{3}\otimes\mathcal{H}^{N}_{4}\otimes\mathcal{H}^{N}_{5}\otimes\mathcal{H}^{N}_{6}\otimes\mathcal{H}^{N}_{7},$
(22)

forming the input of a quantum circuit as in Fig. 2.

$\Qcircuit@C=1em@R=2em@!R{&\lstick{1}\qw\qw\\\
\lstick{2}\qw\qw\inputgroupv{1}{2}{1.2em}{1em}{\ket{\text{rigorous}}\;\qquad\quad}\\\
\lstick{\ket{\text{mathematicians}}\;3}\qw\qw\\\ \lstick{4}\qw\qw\\\
\lstick{5}\qw\qw\\\
\lstick{6}\qw\qw\inputgroupv{4}{6}{1.2em}{2em}{\ket{\text{and}}\;\quad}\\\
\lstick{\ket{\text{physicists}}\;7}\qw\qw}$ Figure 2: Quantum circuit with
syntactically ambiguous input.

From here, different contractions, corresponding to the two possible readings,
will be represented by different circuits acting on this same input, as we
show in detail below.

###  III.2 Contraction as measurement of permutation operator

To compute the desired contraction using the quantum circuit, we calculate the
expectation value of the permutation operator $\widehat{P}_{ij}$ on the input
states/wires indexed by $i,j$. These correspond to the spaces with elements
that we want to contract, following the syntactic rules. For two states
$\ket{\phi_{1}}_{i}$ and $\ket{\phi_{2}}_{j}$ belonging to two numbered copies
of a Hilbert space, respectively $\mathcal{H}^{\lceil A\rceil}_{i}$ and
$\mathcal{H}^{\lceil A\rceil}_{j}$, we refer to the following quantity as the
measurement of the expectation value of the permutation operator:

$\displaystyle\bra{\phi_{1}}_{i}\bra{\phi_{2}}_{j}\widehat{P}_{ij}\ket{\phi_{1}}_{i}\ket{\phi_{2}}_{j}=$
$\displaystyle=\innerproduct{\phi_{1}}{\phi_{2}}_{i}\innerproduct{\phi_{2}}{\phi_{1}}_{j}\equiv\left|\innerproduct{\phi_{1}}{\phi_{2}}\right|^{2}.$
(23)

In general, to obtain this quantity on a quantum circuit, one must perform
repeated measurements of the input states $\ket{\phi_{1}}_{i}$ and
$\ket{\phi_{2}}_{j}$, on a basis that diagonalizes the permutation operator,
summing the frequency of outcomes, using the respective operator’s eigenvalues
as weights. We introduce the following circuit notation to indicate the
measurement of the permutation operator:

$\Qcircuit@C=1em@R=2em@!R{&\lstick{i}\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{ij}$\@add@centering}}\\\
\lstick{j}\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{ij}$\<EMAIL_ADDRESS>
If the measuring device is only capable of performing measurements in the
standard basis, then we must additionally apply to the input states the
inverse of the transformation that diagonalizes the permutation operator,
before performing the repeated measurements. In appendix A we show how this
can be achieved using the inverse transformation to the Bell basis in the case
of two-qubit inputs.

We now show in two ways that the final representation of a simple sentence
such as Alice talks is stored as an effective state $\ket{\psi}$ in
$\mathcal{H}^{S}_{3}$, not normalized for clarity, after measuring
$\widehat{P}_{12}$, with input as given in Eq. (20).

##### Using operators.

Assume that an operator $\widehat{O}_{3}$ is being measured in space
$\mathcal{H}^{S}_{3}$. Its expectation value is given by
$\bra{\psi}\widehat{O}_{3}\ket{\psi}$, after measuring $\widehat{P}_{12}$,
with

$\bra{\text{Alice}}\bra{\text{talks}}\widehat{P}_{12}\otimes\widehat{O}_{3}\ket{\text{Alice}}\ket{\text{talks}}\equiv\bra{\psi}\widehat{O}_{3}\ket{\psi}.$
(24)

The left-hand side unfolds as follows:

$\displaystyle\bra{\text{Alice}}\bra{\text{talks}}\;\widehat{P}_{12}\otimes\widehat{O}_{3}\;\ket{\text{Alice}}\ket{\text{talks}}=$
$\displaystyle=\sum_{pqr,p^{\prime}q^{\prime}r^{\prime}}A^{*}_{p}t^{*}_{qr}\bra{n_{p}n_{q}s_{r}}\;\widehat{P}_{12}\otimes\widehat{O}_{3}\;A_{p^{\prime}}t_{q^{\prime}r^{\prime}}\ket{n_{p^{\prime}}n_{q^{\prime}}s_{r^{\prime}}}$
$\displaystyle=\sum_{pqr,p^{\prime}q^{\prime}r^{\prime}}A^{*}_{p}t^{*}_{qr}\bra{n_{p}n_{q}s_{r}}\;\widehat{O}_{3}\;A_{p^{\prime}}t_{q^{\prime}r^{\prime}}\ket{n_{q^{\prime}}n_{p^{\prime}}s_{r^{\prime}}}$
$\displaystyle=\sum_{pqr,p^{\prime}q^{\prime}r^{\prime}}A^{*}_{p}t^{*}_{qr}\bra{s_{r}}\;\widehat{O}_{3}\;A_{p^{\prime}}t_{q^{\prime}r^{\prime}}\ket{s_{r^{\prime}}}\delta_{pq^{\prime}}\delta_{qp^{\prime}}$
$\displaystyle=\sum_{qr,q^{\prime}r^{\prime}}A_{q}t^{*}_{qr}\bra{s_{r}}\;\widehat{O}_{3}\;A^{*}_{q^{\prime}}t_{q^{\prime}r^{\prime}}\ket{s_{r^{\prime}}}.$
(25)

To uniquely determine $\ket{\psi}$, we need to solve $m=d(d-1)/2$ independent
equations, where $d$ is the dimension of $\mathcal{H}^{3}$, of the form below

$\sum_{qr,q^{\prime}r^{\prime}}A_{q}t^{*}_{qr}\bra{n_{r}}\;\widehat{O}_{3}\;A^{*}_{q^{\prime}}t_{q^{\prime}r^{\prime}}\ket{s_{r^{\prime}}}=\bra{\psi}\widehat{O}_{3}\ket{\psi}.$
(26)

Any operator $\widehat{O}_{3}$ can be decomposed as a sum of $m$ linearly
independent operators $\widehat{O}^{a}_{3}$, with $1<a<m$. Since Eq. (26)
holds for any operator, then it holds for each $\widehat{O}^{a}_{3}$, thus
generating $m$ independent equations, necessary and sufficient to solve for
$\ket{\psi}$. In particular, if $\ket{\psi}$ is expressed in the basis
$\ket{s_{r^{\prime}}}$, the components of $\ket{\psi}$ are given precisely by
the respective components of the left-hand side of Eq. (26), from which we can
immediately conclude that the effective state in $\mathcal{H}_{S}^{3}$ is

$\ket{\psi}=\sum_{q^{\prime}r^{\prime}}A^{*}_{q^{\prime}}t_{q^{\prime}r^{\prime}}\ket{s_{r^{\prime}}}\equiv\llbracket\text{Alice
talks}\rrbracket.\qquad\blacksquare$ (27)

Similarly, density matrices can be used to confirm not only that the state in
$\mathcal{H}^{S}_{3}$ corresponds to Eq. (27) after the measurement, using
partial tracing, but also that the outcome of this operation is a pure state.

##### Using density matrices.

Assume that the sentence Alice talks is being represented by the pure state
density matrix

$\widehat{\rho}=\ket{\text{Alice}}\ket{\text{talks}}\bra{\text{Alice}}\bra{\text{talks}}.$
(28)

We want to show that the density matrix $\widehat{\rho}_{3}$ that we obtain in
space $\mathcal{H}_{3}^{S}$ after the measurement of $\widehat{P}_{12}$ is in
fact a pure state. We do that by taking the partial trace in spaces $1$ and
$2$ of $\widehat{P}_{12}\widehat{\rho}$:

$\displaystyle\widehat{\rho}_{3}=\Tr_{12}\left(\widehat{P}_{12}\widehat{\rho}\right)=$
$\displaystyle=\sum_{ab}\sum_{pqr,p^{\prime}q^{\prime}r^{\prime}}\bra{n_{a}n_{b}}\widehat{P}_{12}A_{p^{\prime}}t_{q^{\prime}r^{\prime}}\ket{n_{p^{\prime}}n_{q^{\prime}}s_{r^{\prime}}}$
$\displaystyle\cdot\bra{n_{p}n_{q}s_{r}}A^{*}_{p}t^{*}_{qr}\ket{n_{a}n_{b}}$
$\displaystyle=\sum_{ab}\sum_{pqr,p^{\prime}q^{\prime}r^{\prime}}\bra{n_{a}n_{b}}A_{p^{\prime}}t_{q^{\prime}r^{\prime}}\ket{n_{q^{\prime}}n_{p^{\prime}}s_{r^{\prime}}}$
$\displaystyle\cdot\bra{n_{p}n_{q}s_{r}}A^{*}_{p}t^{*}_{qr}\ket{n_{a}n_{b}}$
$\displaystyle=\sum_{r,p^{\prime}q^{\prime}r^{\prime}}A_{p^{\prime}}t_{q^{\prime}r^{\prime}}\ket{s_{r^{\prime}}}\bra{s_{r}}A^{*}_{q^{\prime}}t^{*}_{p^{\prime}r}$
$\displaystyle=\sum_{q^{\prime}r^{\prime}}A^{*}_{q^{\prime}}t_{q^{\prime}r^{\prime}}\ket{s_{r^{\prime}}}\sum_{p^{\prime}r}\bra{s_{r}}A_{p^{\prime}}t^{*}_{p^{\prime}r}=\ket{\psi}\bra{\psi}.$
(29)

This thus shows that the resulting state in space $\mathcal{H}_{3}^{S}$ is
pure and equal to Eq. 27. $\blacksquare$

Note that here the index contraction is equivalent to that of Eq. (9),
enhanced with the conjugation of some components, which remain as an
informative feature from the directionality of language, which would be lost
otherwise. The circuit that calculates Eq. (27) is given in Fig. 3.

$\Qcircuit@C=1em@R=2em@!R{&\lstick{\ket{\text{Alice}}\;1}\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{12}$\@add@centering}}\\\
\lstick{2}\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{12}$\@add@centering}}\\\
\lstick{3}\qw\qw\inputgroupv{2}{3}{1.2em}{1.5em}{\ket{\text{talks}}\qquad}.}$
Figure 3: Quantum circuit that measures the permutation operator
$\widehat{P}_{12}$ on an intransitive sentence input.

An alternative way of contracting the two-qubit spaces has been proposed in
Ref. [16], where the Bell effect
$\bra{\beta_{00}}\equiv\left(\bra{00}+\bra{11}\right)/\sqrt{2}\in\mathcal{H}_{N}^{1}\,\otimes\,\mathcal{H}_{N}^{2}$
is measured instead as

$\displaystyle\llbracket\text{Alice
talks}\rrbracket=\bra{\beta_{00}}\ket{\text{Alice}}\ket{\text{talks}}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\sum_{p^{\prime}q^{\prime}r^{\prime}}\left(\bra{00}+\bra{11}\right)A_{p^{\prime}}t_{q^{\prime}r^{\prime}}\ket{\hat{n}_{p^{\prime}}\hat{n}_{q^{\prime}}\hat{s}_{r^{\prime}}}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\sum_{r^{\prime}}\left(A_{0}t_{0r^{\prime}}+A_{1}t_{1r^{\prime}}\right)\ket{\hat{s}_{r^{\prime}}}.$
(30)

Measuring the permutation operator as we do in Eq. (III.2) is manifestly a
more general way of contracting the representations of words than what is done
in Eq. (III.2). On the one hand, it allows each interpretation space to have
more than two basis states, that is, each quantum wire can represent something
more general than one qubit. On the other hand, it accommodates correctly the
existence of complex numbers in the quantum mechanical representations.
Importantly, it has also one more important feature that we will make use of
now: it allows us to integrate a quantum superposition of conflicting
readings.

###  III.3 Ambiguous readings on a quantum circuit

$\Qcircuit@C=1em@R=2em@!R{&\lstick{1}\qw\qw\qw\qw\\\
\lstick{2}\qw\multimeasure{3}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{25}$\@add@centering}}\inputgroupv{1}{2}{1.2em}{1.4em}{\ket{\text{rigorous}}\;\qquad\quad}\\\
\lstick{\ket{\text{mathematicians}}\;3}\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{34}$\@add@centering}}\\\
\lstick{4}\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{34}$\@add@centering}}\\\
\lstick{5}\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{25}$\@add@centering}}\\\
\lstick{6}\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}\inputgroupv{4}{6}{1.2em}{3em}{\ket{\text{and}}\;\quad}\\\
\lstick{\ket{\text{physicists}}\;7}\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}}$ Figure 4: Quantum circuit for the first
interpretation of the syntactically ambiguous phrase.
$\Qcircuit@C=1em@R=2em@!R{&\lstick{1}\qw\multimeasure{3}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{14}$\@add@centering}}\\\
\lstick{2}\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{23}$\@add@centering}}\inputgroupv{1}{2}{1.2em}{1.4em}{\ket{\text{rigorous}}\;\qquad\quad}\\\
\lstick{\ket{\text{mathematicians}}\;3}\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{23}$\@add@centering}}\\\
\lstick{4}\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{14}$\@add@centering}}\\\ \lstick{5}\qw\qw\qw\qw\\\
\lstick{6}\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}\inputgroupv{4}{6}{1.2em}{3em}{\ket{\text{and}}\;\quad}\\\
\lstick{\ket{\text{physicists}}\;7}\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}}$ Figure 5: Quantum circuit for the second
reading of the syntactically ambiguous phrase.

The two readings in Eqs. (II.2) and (II.2) can be represented respectively by
the two different circuits in Figs. 4 and 5, expressing different contraction
schemes. To express the two readings simultaneously, we refer to the analysis
of syntactic ambiguities already developed in Ref. [11], which we here
implement. We can go from the first reading to the second by applying two swap
gates. First, we swap wires $3$ and $5$ on the second reading, which turns the
measurement of $\widehat{P}_{23}$ into the measurement of $\widehat{P}_{25}$.
Next, by swapping wires $5$ (which now contains the information from wire $3$)
and $1$, we effectively turn the measurement of $\widehat{P}_{14}$ into the
measurement of $\widehat{P}_{34}$. In this way, the circuit in Fig. 6 is
equivalent to that of the first reading. If we control the application of this
set of swap gates on an extra qubit $\ket{c}=c_{1}\ket{1}+c_{2}\ket{0}$, we
entangle the states of this qubit with the two possible readings. The first
reading is stored in the quantum wire $5$ with probability $|c_{1}|^{2}$,
while the second reading is stored in that same quantum wire with probability
$|c_{2}|^{2}$. In total we have what is represented in the circuit of Fig. 7.

$\Qcircuit@C=1em@R=2em@!R{&\lstick{1}\qw\qswap\qwx[4]\qw\multimeasure{3}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{14}$\@add@centering}}\\\
\lstick{2}\qw\qw\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{23}$\@add@centering}}\inputgroupv{1}{2}{1.2em}{1.4em}{\ket{\text{rigorous}}\;\qquad\quad}\\\
\lstick{\ket{\text{mathematicians}}\;3}\qswap\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{23}$\@add@centering}}\\\
\lstick{4}\qw\qwx\qw\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{14}$\@add@centering}}\\\
\lstick{5}\qswap\qwx\qswap\qw\qw\qw\qw\\\
\lstick{6}\qw\qw\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}\inputgroupv{4}{6}{1.2em}{3em}{\ket{\text{and}}\;\quad}\\\
\lstick{\ket{\text{physicists}}\;7}\qw\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}}$ Figure 6: Quantum circuit that computes
the first reading from the contractions of the second, and is therefore
equivalent to Fig. 4.
$\Qcircuit@C=1em@R=2em@!R{&\lstick{1}\qw\qswap\qwx[6]\qw\multimeasure{3}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{14}$\@add@centering}}\\\
\lstick{2}\qw\qw\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{23}$\@add@centering}}\inputgroupv{1}{2}{1.2em}{1.4em}{\ket{\text{rigorous}}\;\qquad\quad}\\\
\lstick{\ket{\text{mathematicians}}\;3}\qswap\qwx[4]\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{23}$\@add@centering}}\\\
\lstick{4}\qw\qw\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{14}$\@add@centering}}\\\ \lstick{5}\qswap\qswap\qw\qw\qw\qw\\\
\lstick{6}\qw\qw\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}\inputgroupv{4}{6}{1.2em}{3em}{\ket{\text{and}}\;\quad}\\\
\lstick{\ket{\text{physicists}}\;7}\qw\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}\\\
\lstick{\ket{c}\;\;}\ctrl{-1}\ctrl{-1}\qw\qw\qw\qw}$ Figure 7: Quantum circuit
that computes simultaneously the two readings from the ambiguous input.

The innovation that this implementation brings is that we are now able to deal
with both interpretations simultaneously, that later contractions, with the
representations of other words, have the potential to disambiguate.

##  IV Application

In this section we apply Grover’s quantum search algorithm to obtain the
answer to a wh-question with quantum speedup, using the quantum circuits for
sentence representation developed in the previous section.

###  IV.1 Grover’s quantum search algorithm

Grover’s quantum search algorithm aims at finding the correct answer to a
query, by taking a state with an equal superposition of orthogonal states
representing the answers as the input, and outputting a state in which the
only basis states that have any probability of being measured correspond to
correct answers. For $P=2^{p}$ possible solutions, the first step is to
generate a linear superposition of $P$ unique states, with its index $x$
corresponding to one of the possible solutions. In the original proposal [35],
this input state is obtained by acting on $\ket{0}^{\otimes p}$ qubit states
with the $H^{\otimes p}$ gate, where $H$ is the one-qubit Hadamard gate, which
generates

$\ket{\Psi}=\frac{1}{\sqrt{P}}\sum_{x=0}^{P-1}\ket{x}.$ (31)

Then, a sequence of gates, the Grover iteration, is repeatedly applied to this
input state, until a correct answer is the guaranteed outcome of the
measurement of the initial qubits. For $Q$ correct solutions, only
$O(\sqrt{P/Q})$ iterations are necessary, representing a quadratic speedup
compared to a classical search algorithm, which requires checking all $P$
possible answers. Each Grover iteration $G$ has two main components: first, an
oracle operation $O$, and then an inversion about the mean operation, formed
by applying the unitary transformation that generates $\ket{\Psi}$ to
$2\ket{0}\bra{0}-1$, in this case

$H^{\otimes p}(2\ket{0}\bra{0}-1)H^{\otimes p}\equiv 2\ket{\Psi}\bra{\Psi}-1,$
(32)

which can easily be shown to be unitary. The heart of the algorithm is the
oracle, as it is able to distinguish the answers that are correct from those
that are not. It is a unitary operation that works by flipping the sign of the
answer state if $\ket{x}$ is correct, that is,

$\displaystyle\left\\{\begin{matrix}&O(\ket{x})=-\ket{x}&\text{if}\ket{x}\text{is
a correct answer,}\\\
&O(\ket{x})=\ket{x}&\text{otherwise}.\end{matrix}\right.$

To achieve this, more qubits might be necessary, and those constitute the
“oracle workspace”. In the original setup, it is the oracle that depends on
the query at hand, as well as the form of the inputs, while the inverse
operation has a universal form. By representing our wh-question query as
quantum states and contractions therein, we will see that we can use Grover’s
algorithm with the problem-dependence of its parts reversed: instead it is the
oracle that is universal, and the rotation is query-dependent, obtained from a
unitary transformation on $\ket{0}$.

###  IV.2 Question/answering input-state preparation

The question statement and possible answers hold the key for the search
algorithm to identify the correct answers in our application. This will happen
as a consequence of the contractions of the possible solutions with the
question predicate. We will use our previous construction as the input of the
first Grover iteration. To this end, suppose that we want to know the answer
to the question Who talks?, and that we have $P$ possible answers, of which
$Q$ are absolutely correct, and $P-Q$ are, on the contrary, definitely wrong.
For the oracle to identify the correct answers, they must be produced from the
contraction with the verb, and they must be in a superposition equivalent to
Eq. (31).

The more complex mapping of $w$ to the semantics, when compared with the
syntactic types $s$ and $n$, can be attributed to the particular semantics of
questions and our application. In standard terms, the meaning of a question is
taken as the map that sends answers, which belong to the interpretation space
of nouns, to truth values, which are elements of the interpretation space of
declarative sentences. We want to keep track of which word provides a correct
answer in our quantum circuit, and a map like the latter, upon performing
contractions, would only give us a count of how many correct and wrong answers
there are.

As such, this map needs to be furthermore tensored with elements of
$\mathcal{H}^{\otimes p}$, of which each of the basis elements corresponds to
the unique indexing of the possible answers. This provides an entanglement
between the distributional representation of a noun, its corresponding truth
value and an enumerable representation in the quantum circuit.

The word who thus belongs to the following semantic space, in the image of Eq.
(II.2),

$\lceil w/(n\backslash s)\rceil=\mathcal{H}^{\otimes
p}\otimes\mathcal{H}^{N}\otimes\mathcal{H}^{\otimes
p}\otimes\mathcal{H}^{S}\otimes\mathcal{H}^{S}\otimes\mathcal{H}^{N},$

with semantic representation given as

$\displaystyle\ket{\text{who}}=\sum_{ab,ij,kl}\ket{a}_{1}\ket{n_{i}}_{2}\ket{b}_{4}\ket{s_{j}}_{3}\ket{s_{k}}_{5}\ket{n_{l}}_{6}\delta_{ab}\delta_{ik}\delta_{jl}=$
$\displaystyle=\sum_{a,i,l}\ket{a}_{1}\ket{n_{i}}_{2}\ket{a}_{3}\ket{s_{l}}_{4}\ket{n_{i}}_{5}\ket{s_{l}}_{6}.$
(33)

The intransitive verb talks has the same representation as before, now with
the adapted labeling of wires

$\ket{\text{talks}}=\sum_{mn}t_{mn}\;\ket{n_{m}}_{7}\ket{s_{n}}_{8}.$ (34)

The semantic contraction of who with talks, following the interpretation of
the syntactic contraction, results in

$\displaystyle\bra{\text{who}}\bra{\text{talks}}\;\widehat{P}_{67}\otimes\widehat{P}_{58}\otimes\widehat{O}_{1234}\;\ket{\text{who}}\ket{\text{talks}}$
$\displaystyle=\sum_{a^{\prime}i^{\prime}l^{\prime}m^{\prime}n^{\prime}}\bra{a^{\prime}}_{1}\bra{n_{i^{\prime}}}_{2}\bra{a^{\prime}}_{3}\bra{s_{l^{\prime}}}_{4}\bra{n_{i^{\prime}}}_{5}\bra{s_{l^{\prime}}}_{6}$
(35) $\displaystyle\cdot
t^{*}_{m^{\prime}n^{\prime}}\bra{n_{m^{\prime}}}_{7}\bra{s_{n^{\prime}}}_{8}\widehat{O}_{1234}\;\sum_{ailmn}\ket{a}_{1}\ket{n_{i}}_{2}\ket{a}_{3}\ket{s_{l}}_{4}$
$\displaystyle\cdot\ket{n_{m}}_{5}\ket{s_{n}}_{6}t_{mn}\ket{n_{i}}_{7}\bra{s_{l}}_{8}$
$\displaystyle=\sum_{a^{\prime}i^{\prime}l^{\prime}m^{\prime}n^{\prime}}\bra{a^{\prime}}_{1}\bra{n_{i^{\prime}}}_{2}\bra{a^{\prime}}_{3}\bra{s_{l^{\prime}}}_{4}t^{*}_{m^{\prime}n^{\prime}}$
$\displaystyle\cdot\widehat{O}_{1234}\;\ket{a}_{1}\ket{n_{m^{\prime}}}_{2}\ket{a}_{3}\ket{s_{n^{\prime}}}_{4}t_{i^{\prime}l^{\prime}}$
$\displaystyle=\sum_{a^{\prime}i^{\prime}l^{\prime}}t_{i^{\prime}l^{\prime}}\bra{a^{\prime}}_{1}\bra{n_{i^{\prime}}}_{2}\bra{a^{\prime}}_{3}\bra{s_{l^{\prime}}}_{4}$
$\displaystyle\cdot\widehat{O}_{1234}\;\sum_{ail}t^{*}_{il}\ket{a}_{1}\ket{n_{i}}_{2}\ket{a}_{3}\ket{s_{l^{\prime}}}_{4}.$
(36)

From this we read off the question representation, rewriting the indices:

$\llbracket\text{who
talks}\rrbracket=\sum_{ail}t^{*}_{il}\ket{a}_{1}\ket{n_{i}}_{2}\ket{a}_{3}\ket{s_{l}}_{4}.$
(37)

To be the input of the quantum search algorithm, the full input needs to
correspond to an equal superposition of all possible answers. This can be
achieved by entangling the distributional representation of the answers with
the corresponding index

$\ket{\text{answers}}=\sum_{bp}W_{p}^{b}\ket{n_{p}}_{9}\ket{b}_{10},$ (38)

followed by a contraction with the question representation, which happens
strictly at the semantic level. Hence

$\displaystyle\bra{\text{who
talks}}\bra{\text{answers}}\widehat{P}_{29}\otimes\widehat{P}_{1,10}\otimes\widehat{O}_{34}$
$\displaystyle\cdot\ket{\text{who talks}}\ket{\text{answers}}=$
$\displaystyle\sum_{a^{\prime}i^{\prime}l^{\prime}}t_{i^{\prime}l^{\prime}}\bra{a^{\prime}}_{1}\bra{n_{i^{\prime}}}_{2}\bra{a^{\prime}}_{3}\bra{s_{l^{\prime}}}_{4}\sum_{b^{\prime}p^{\prime}}W_{p^{\prime}}^{*b^{\prime}}\bra{n_{p^{\prime}}}_{9}\bra{b^{\prime}}_{10}$
$\displaystyle\cdot\widehat{O}_{34}\sum_{ail}t^{*}_{il}\ket{b}_{1}\ket{n_{p}}_{2}\ket{a}_{3}\ket{s_{l}}_{4}\sum_{bp}W_{p}^{b}\ket{n_{i}}_{9}\ket{a}_{10}$
$\displaystyle=\sum_{a^{\prime}i^{\prime}l^{\prime}}W^{a^{\prime}}_{i^{\prime}}t_{i^{\prime}l^{\prime}}\bra{a^{\prime}}_{3}\bra{s_{l^{\prime}}}_{4}$
$\displaystyle\cdot\widehat{O}_{34}\sum_{amn}W^{*a}_{i}t^{*}_{il}\ket{a}_{3}\ket{s_{l}}_{4},$
(39)

such that the effective input state to the Grover’s algorithm is

$\ket{\Psi_{initial}}=\sum_{ail}W^{*a}_{i}t^{*}_{il}\ket{a}_{3}\ket{s_{l}}_{4},$
(40)

which represents an entanglement between the indices of possible answers and
truth values. This process is represented by the circuit in Fig. 8.

$\Qcircuit@C=1em@R=2em@!R{&\lstick{1}\qw\qw\qw\multimeasure{9}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{1,10}$\@add@centering}}\\\
\lstick{2}\qw\qw\multimeasure{7}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{29}$\@add@centering}}\\\ \lstick{3}\qw\qw\qw\qw\qw\qwa\\\
\lstick{4}\qw\qw\qw\qw\qw\qwa\\\
\lstick{5}\qw\multimeasure{3}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{58}$\@add@centering}}\\\
\lstick{6}\multimeasure{1}{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}\\\
\lstick{7}\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{67}$\@add@centering}}\\\
\lstick{8}\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{58}$\@add@centering}}\\\
\lstick{9}\qw\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{29}$\@add@centering}}\\\ \lstick{\quad
10}\qw\qw\qw\ghost{\parbox{19.91684pt}{\centering$\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
10.00002pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ellipse
ur,_{}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{}\ignorespaces{}}}}}$\\\
$\widehat{P}_{1,10}$\@add@centering}}\inputgroupv{1}{6}{1.5em}{7.2em}{\ket{\text{who}}\qquad}\inputgroupv{7}{8}{1.5em}{1.3em}{\ket{\text{talks}}\qquad}\inputgroupv{9}{10}{1.5em}{1.3em}{\ket{\text{answers}}\qquad\quad\;}}$
Figure 8: Quantum circuit that generates the input of the first Grover
iteration for question-answering.

###  IV.3 Oracle and inversion

Grover’s algorithm requires a normalized state as initial input. Since the
amplitudes in the state in Eq. (40) have information about whether a certain
answer is correct, they uniquely associate each word indexed by $a$ with one
of the basis states $\ket{s_{l}}$, in such a way that
$\sum_{i}W^{*a}_{i}t^{*}_{il}$ is null if the combination between word index
$a$ and truth value $l$ is not correct, and otherwise equal to one. Since
every word should be either true or false, that leaves us with precisely $P$
independent and equally summed states. Therefore, if the indices $al$ are
abbreviated by one index $x$, the normalized state is given as

$\ket{\Psi_{initial}}=\frac{1}{\sqrt{P}}\sum_{x=0}^{P-1}\ket{x},$ (41)

with

$\ket{x}=\sum_{i}W^{*a}_{i}t^{*}_{il}\ket{a}_{3}\ket{s_{l}}_{4}.$ (42)

The oracle applied to this input state takes the form of the circuit in Fig.
9.

$\Qcircuit@C=1em@R=2em@!R{&\lstick{3}\qw\qw\qw\ctrl{2}\qw\qwa\\\
\lstick{4}\qw\qw\qw\qw\qw\qwa\inputgroupv{1}{2}{1.2em}{1.5em}{\ket{\Psi_{initial}}\qquad\quad}\\\
\lstick{\ket{0}\;11}\gate{H}\gate{X}\qw\targ\qw\qwa}$ Figure 9: Oracle for
question-answering.

The states $\ket{a}$ on the first $p$ qubits, being in one-to-one
correspondence with each of the possible solutions, are the complete set of
states that build up the equal superposition $\ket{\Psi}=H^{\otimes
p}\ket{0}^{\otimes p}$, as in Eq. (31). In terms of the states that correspond
to words that are correct or incorrect, we can rewrite $\ket{\Psi}$ as

$\ket{\Psi}=\sin(\frac{\theta}{2})\ket{\alpha}_{3}+\cos(\frac{\theta}{2})\ket{\beta}_{3},$
(43)

with $\ket{\alpha}$ the normalized sum of all states that correspond to words
that are not solutions, and $\ket{\beta}$ to the normalized sum of those that
correspond to words that are solutions. Using this notation, the
$\ket{\Psi_{initial}}$ state that we obtain using the contractions can be
expressed as

$\ket{\Psi_{initial}}=\sin(\frac{\theta}{2})\ket{\alpha}_{3}\ket{0}_{4}+\cos(\frac{\theta}{2})\ket{\beta}_{3}\ket{1}_{4}.$
(44)

Though there is entanglement between the first $p$ qubits and the last one,
this is a pure state in the $p+1$ qubit space, as it results from the
measurement of the permutation operators, as shown in Sec. III.2. As such,
there is a unitary transformation that generates it from $\ket{0}^{\otimes
p+1}$ as

$\ket{\Psi_{initial}}=U\ket{0}^{p+1}.$ (45)

Using this, we can construct the rotation part of the Grover algorithm as

$U(2\ket{0}\bra{0}-1)U^{\dagger}=2\ket{\Psi_{initial}}\bra{\Psi_{initial}}-1.$
(46)

It follows that the Grover iteration applied on the input state in Eq. (44)
using the oracle and the rotation in Eq. (46) gives the desired outcome of

$\displaystyle(2\ket{\Psi_{initial}}\bra{\Psi_{initial}}-1)O(\ket{\Psi_{initial}})=$
$\displaystyle\sin(\frac{3\theta}{2})\ket{\alpha}_{3}\ket{0}_{4}+\cos(\frac{3\theta}{2})\ket{\beta}_{3}\ket{1}_{4}.$
(47)

This is precisely what we expect to obtain. For the second iteration, the
oracle acts as desired, and so does the rotation. After a number of iterations
only the states associated with $\ket{1}_{4}$ have positive amplitude, which
means that we are certain to measure the index of a word that corresponds to a
correct answer when we make a measurement on the first $p$ qubits. Thus we
have obtained a correct answer with quadratic speedup due to the quantum
search algorithm.

##  V Conclusion and Outlook

In this paper we introduced two main developments in the application of
quantum computation to natural language processing. The first one is a tensor-
contraction scheme on quantum circuits. Taking quantum states as the
representations of all input words, contractions are then identified with the
expectation value of an appropriate permutation operator. Doing this, are we
not only able to reproduce previous analytical results, but we also allow for
complex values and create quantum circuits that are equipped to deal with the
syntactic ambiguities in Ref. [11]. With this setup, each reading of an
ambiguous phrase corresponds to a particular circuit, and different readings
are interchangeable upon the application of a number of swap gates.
Controlling on these swap gates, we can obtain a true quantum superposition of
the multiple readings. This covers the problem of how to deal with multiple
readings in real time, without the need to assume any contextualization. While
this addresses the question of syntactic ambiguities by making use of the
quantum superposition principle, ambiguities at the word level can be
immediately accommodated for by using density matrices [6, 7, 8, 36], instead
of the pure states we use here for simplicity. A generalization to other
sentence-level ambiguities constitutes further work, in the expectation that
the use of different controls allows for different readings simultaneously in
the output state.

The second development builds on this quantum framework, and consists of a
quantum search algorithm that is able to find the answer to a wh-question with
quantum speedup. As input, the algorithm takes a multi-partite state in
quantum superposition, representing a wh-question and its possible answers,
and performs a series of tensor contractions as established previously. A
series of gates then acts repeatedly on the post-contraction state,
guaranteeing that a correct answer to the question is obtained upon a single
final measurement. Our algorithm takes advantage of intrinsic quantum features
to identify and deliver a correct answer with quantum speedup of quadratic
order, when compared to the classical alternative of checking every possible
answer. We are thus able to provide a correct answer using information given
directly by the tensor contractions of representations of words as proposed by
DisCoCat, and without needing to hand-feed any labels nor to learn the answers
to other questions. Our approach thus shows how quantum circuit
implementations can break with the widely accepted “learning paradigm” of
current NLP approaches to question-answering and other tasks used in Ref.
[17], providing a scalable approach to open-ended questions. Our approach
differs from that of Ref. [13] also in the sense that we keep all words as
input states, instead of representing words from complex types as gates that
modify circuit inputs, remaining closer to the compositional spirit of the
syntax and therefore being more easily extensible to larger language
fragments. Further work includes finding an effective implementation of the
measurement of the permutation operator for an arbitrary number of qubits,
possibly making use of the Hadamard test [37], and understanding how to find a
universal form of the inversion operator that does not depend on
$\ket{\alpha}$ and $\ket{\beta}$ separately. An extension of the present
formalism can furthermore account for a better understanding of the temporal
evolution of the meanings of sentences.

##  VI Acknowledgements

This work is supported by the Utrecht University’s Complex Systems Fund, with
special thanks to Peter Koeze, and the D-ITP consortium, a program of the
Netherlands Organization for Scientific Research (NWO) that is funded by the
Dutch Ministry of Education, Culture and Science (OCW).

##  Appendix A Measuring the permutation operator on two qubits

In this appendix we show that for the measurement of the permutation operator
applied to two qubits it suffices to measure the input states in the Bell
basis. The two input qubits have the four possible joint states in the
standard basis, given by

$\ket{00}=\begin{pmatrix}1\\\ 0\\\ 0\\\
0\end{pmatrix},\ket{10}=\begin{pmatrix}0\\\ 1\\\ 0\\\
0\end{pmatrix},\ket{01}=\begin{pmatrix}0\\\ 0\\\ 1\\\
0\end{pmatrix},\ket{11}=\begin{pmatrix}0\\\ 0\\\ 0\\\ 1\end{pmatrix}.$ (48)

The permutation operator applied to two qubits is equivalent to the swap gate
$S$. In this basis, this operator has the matrix representation

$S=\begin{pmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\ 0&0&0&1\end{pmatrix}.$ (49)

The eigenstates of this operator are the well-known singlet and triplet states
that represent the joint spin of two spin-$1/2$ particles. With eigenvalue
$-1$, we have the singlet state

$\ket{0,0}=\frac{1}{\sqrt{2}}\begin{pmatrix}0\\\ -1\\\ 1\\\ 0\end{pmatrix},$
(50)

and with eigenvalue $1$ we have the three triplet states

$\ket{1,-1}=\begin{pmatrix}1\\\ 0\\\ 0\\\
0\end{pmatrix},\ket{1,0}=\frac{1}{\sqrt{2}}\begin{pmatrix}0\\\ 1\\\ 1\\\
0\end{pmatrix},\text{ and }\ket{1,1}=\begin{pmatrix}0\\\ 0\\\ 0\\\
1\end{pmatrix},$ (51)

expressed in the standard basis as

$\displaystyle\ket{0,0}=\frac{1}{\sqrt{2}}(\ket{01}-\ket{10}),$ (52)
$\displaystyle\ket{1,-1}=\ket{00},$ (53)
$\displaystyle\ket{1,0}=\frac{1}{\sqrt{2}}(\ket{01}+\ket{10}),$ (54)
$\displaystyle\ket{1,1}=\ket{11}.$ (55)

In its turn, the Bell basis can be expressed in terms of the standard basis in
the following way

$\displaystyle\ket{\beta_{00}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11}),$ (56)
$\displaystyle\ket{\beta_{01}}=\frac{1}{\sqrt{2}}(\ket{00}-\ket{11}),$ (57)
$\displaystyle\ket{\beta_{10}}=\frac{1}{\sqrt{2}}(\ket{01}+\ket{10}),$ (58)
$\displaystyle\ket{\beta_{11}}=\frac{1}{\sqrt{2}}(\ket{01}-\ket{10}).$ (59)

The Bell states can thus be rewritten using the total-spin eigenstates of $S$,
given in (52) to (55), as:

$\displaystyle\ket{\beta_{00}}=\frac{1}{\sqrt{2}}(\ket{1,-1}+\ket{1,1})$ (60)
$\displaystyle\ket{\beta_{01}}=\frac{1}{\sqrt{2}}(\ket{1,-1}-\ket{1,1})$ (61)
$\displaystyle\ket{\beta_{10}}=\ket{1,0}$ (62)
$\displaystyle\ket{\beta_{11}}=\ket{0,0}.$ (63)

Because any linear combination of degenerate eigenstates is also an eigenstate
of that operator with the same eigenvalue [proof:
$A\vec{v}=\lambda\vec{v},A\vec{w}=\lambda\vec{w}\Rightarrow
A(a\vec{v}+b\vec{w})=\lambda(a\vec{v}+b\vec{w})$], we see that
$\ket{\beta_{00}}$, $\ket{\beta_{01}}$ and $\ket{\beta_{10}}$ are eigenstates
of $S$ with eigenvalue $1$, and $\ket{\beta_{11}}$ is an eigenstate with
eigenvalue $-1$. Therefore, we can conclude that the Bell basis also
diagonalizes the permutation operator, and as such repeated measurements of
the qubits in this basis allows us to directly compute the expectation value
of the operator in the input states. So, for a two-qubit input state

$\ket{\Phi}=\sum_{ij}a_{i}b_{j}\ket{ij},$ (64)

with $i,j\in\\{0,1\\}$, the expectation value of the $S$ operator is given by

$\expectationvalue{S}_{\Phi}=\left|\bra{\beta_{00}}\ket{\Phi}\right|^{2}+\left|\bra{\beta_{01}}\ket{\Phi}\right|^{2}+\left|\bra{\beta_{10}}\ket{\Phi}\right|^{2}-\left|\bra{\beta_{11}}\ket{\Phi}\right|^{2}.$
(65)

If we are in the possession of a measuring device that can only measure in the
standard basis, we must transform our input states with the inverse
transformation that generates the Bell states. This serves to guarantee that
an outcome $\ket{ij}$ is in fact as likely as the measurement of
$\ket{\beta_{ij}}$ if the input states were measured directly in the Bell
basis.

## References

  * Coecke  _et al._ [2010] B. Coecke, M. Sadrzadeh, and S. Clark, Mathematical foundations for a compositional distributional model of meaning, Lambek Festschrift, Linguistic Analysis 36(1–4) , 345 (2010).
  * Coecke  _et al._ [2013] B. Coecke, E. Grefenstette, and M. Sadrzadeh, Lambek vs. lambek: Functorial vector space semantics and string diagrams for lambek calculus, Annals of Pure and Applied Logic 164, 1079 (2013).
  * Lambek [1958] J. Lambek, The mathematics of sentence structure, The American Mathematical Monthly 65, 154 (1958).
  * Lambek [1997] J. Lambek, Type grammar revisited, in  _Logical Aspects of Computational Linguistics, Second International Conference, LACL ’97_ , Lecture Notes in Computer Science, Vol. 1582, edited by A. Lecomte, F. Lamarche, and G. Perrier (Springer, 1997) pp. 1–27.
  * Turney and Pantel [2010] P. D. Turney and P. Pantel, From frequency to meaning: Vector space models of semantics, Journal of Artificial Intelligence Research 37, 141 (2010).
  * Piedeleu  _et al._ [2015] R. Piedeleu, D. Kartsaklis, B. Coecke, and M. Sadrzadeh, Open system categorical quantum semantics in natural language processing, in  _6th International Conference on Algebra and Coalgebra in Computer Science (CALCO’15)_ , edited by L. Moss and P. Sobociński (2015) pp. 267–286.
  * Sadrzadeh  _et al._ [2018] M. Sadrzadeh, D. Kartsaklis, and E. Balkir, Sentence entailment in compositional distributional semantics, Annals of Mathematics and Artificial Intelligence 82, 189 (2018).
  * Bankova  _et al._ [2019] D. Bankova, B. Coecke, M. Lewis, and D. Marsden, Graded hyponymy for compositional distributional semantics, Journal of Language Modelling 6, 225 (2019).
  * Meyer and Lewis [2020a] F. Meyer and M. Lewis, Modelling lexical ambiguity with density matrices, in  _Proceedings of the 24th Conference on Computational Natural Language Learning_ (Association for Computational Linguistics, 2020) pp. 276–290.
  * Shiebler  _et al._ [2020] D. Shiebler, A. Toumi, and M. Sadrzadeh, Incremental monoidal grammars, arXiv:2001.02296 (2020).
  * Correia  _et al._ [2020a] A. D. Correia, M. Moortgat, and H. Stoof, Density matrices with metric for derivational ambiguity, Journal of Applied Logics 7, 795 (2020a).
  * Correia  _et al._ [2020b] A. Correia, H. Stoof, and M. Moortgat, Putting a spin on language: A quantum interpretation of unary connectives for linguistic applications, arXiv:2004.04128. To appear in: Electronic Proceedings of Theoretical Computer Science (2020b).
  * Coecke [2019] B. Coecke, The mathematics of text structure, arXiv:1904.03478 (2019).
  * Biamonte  _et al._ [2017] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017).
  * Meichanetzidis  _et al._ [2020a] K. Meichanetzidis, S. Gogioso, G. De Felice, N. Chiappori, A. Toumi, and B. Coecke, Quantum natural language processing on near-term quantum computers, arXiv:2005.04147 (2020a).
  * Coecke  _et al._ [2020] B. Coecke, G. de Felice, K. Meichanetzidis, and A. Toumi, Foundations for near-term quantum natural language processing, arXiv:2012.03755 (2020).
  * Meichanetzidis  _et al._ [2020b] K. Meichanetzidis, A. Toumi, G. de Felice, and B. Coecke, Grammar-aware question-answering on quantum computers, arXiv:2012.03756 (2020b).
  * Lorenz  _et al._ [2021] R. Lorenz, A. Pearson, K. Meichanetzidis, D. Kartsaklis, and B. Coecke, QNLP in practice: Running compositional models of meaning on a quantum computer, arXiv:2102.12846 (2021).
  * Bender  _et al._ [2021] E. M. Bender, T. Gebru, A. McMillan-Major, and S. Shmitchell, On the dangers of stochastic parrots: Can language models be too big?, in  _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ (2021) pp. 610–623.
  * Ajdukiewicz [1935] K. Ajdukiewicz, Die syntaktische Konnexität, Studia philosophica , 1 (1935).
  * Moortgat [1997] M. Moortgat, Categorial type logics, in  _Handbook of logic and language_ (Elsevier, 1997) pp. 93–177.
  * Soares and Parreiras [2020] M. A. C. Soares and F. S. Parreiras, A literature review on question answering techniques, paradigms and systems, Journal of King Saud University-Computer and Information Sciences 32, 635 (2020).
  * Note [1] This is a common way of turning Q$\&$A into a classification problem, where each close-ended question gets a binary label, depending on whether the answer is true or false. Binary classification problems are some of the most well established applications of machine learning. After finding a way of representing the question statements, usually as single vectors, a number of these labeled statements is used to predict the labels of the hold-out statements.
  * Lin [1998] D. Lin, Automatic retrieval and clustering of similar words, in  _36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Volume 2_ (1998) pp. 768–774.
  * Navigli and Crisafulli [2010] R. Navigli and G. Crisafulli, Inducing word senses to improve web search result clustering, in  _Proceedings of the 3rd Conference on Empirical Methods in Natural Language Processing (EMNLP ’10)_ (2010) pp. 116–126.
  * Nasiruddin [2013] M. Nasiruddin, A state of the art of word sense induction: A way towards word sense disambiguation for under-resourced languages, in  _Proceedings of RECITAL 2013_ (2013) pp. 192–205.
  * Boleda [2020] G. Boleda, Distributional semantics and linguistic theory, Annual Review of Linguistics 6, 213 (2020).
  * [28] B. B. Rieger,  _On distributed representation in word semantics_ (Berkeley, CA: International Computer Science Institute).
  * Harris [1954] Z. S. Harris, Distributional structure, Word 10, 146 (1954).
  * Mikolov  _et al._ [2013] T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean, Distributed representations of words and phrases and their compositionality, arXiv preprint arXiv:1310.4546 (2013).
  * Devlin  _et al._ [2018] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, Bert: Pre-training of deep bidirectional transformers for language understanding, arXiv preprint arXiv:1810.04805 (2018).
  * Wijnholds  _et al._ [2020] G. Wijnholds, M. Sadrzadeh, and S. Clark, Representation learning for type-driven composition, in  _Proceedings of the 24th Conference on Computational Natural Language Learning (CoNLL ’20)_ (2020) pp. 313–324.
  * Giovannetti  _et al._ [2008] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Physical Review Letters 100, 160501 (2008).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Grover [1996] L. K. Grover, A fast quantum mechanical algorithm for database search, in  _Proceedings of the 28th Annual ACM Symposium on Theory of Computing_ (1996) pp. 212–219.
  * Meyer and Lewis [2020b] F. Meyer and M. Lewis, Modelling lexical ambiguity with density matrices, in  _Proceedings of the 24th Conference on Computational Natural Language Learning (CoNLL ’20)_ (2020) pp. 276–290.
  * Aharonov  _et al._ [2009] D. Aharonov, V. Jones, and Z. Landau, A polynomial quantum algorithm for approximating the Jones polynomial, Algorithmica 55, 395 (2009).