Modeling Quantum Entanglements in Quantum Language Models

1 Introduction

Quantum theory (QT) has a profound impact on multidisciplinary studies, such as Physics, Philosophy, Psychology and Information Retrieval (IR) [Heisenberg and Northrop, 1958; Busemeyer and Bruza, 2012; Melucci and van Rijsbergen, 2011; Song et al., 2010; Sordoni et al., 2014]. In a seminal book [van Rijsbergen, 2004], quantum theory was for the first time regarded as "a kind of formal language that can be used for describing objects and processes in IR". Following this pioneering work, the Quantum Probability Ranking Principle (QPRP) was proposed to rank interdependent documents based on the quantum interference [Zuccon and Azzopardi, 2010]. Inspired by the photon polarization, a Quantum Measurement inspired Ranking model (QMR) was introduced [Zhao et al., 2011]. Although the QPRP and the QMR achieved better performances, the probabilities in both methods are not actually calculated according to the QT formulations.

∗Corresponding authors: Yuexian Hou and Peng Zhang.

Piwowarski et al. [2010] explored to express queries as density matrices and documents as subspaces. However, this method did not bring about the excellent performance as expected. Later, a Quantum Language Model (QLM) was proposed to model term dependencies based on the quantum theory and outperformed the conventional IR model [Sordoni et al., 2013]. However, QLM models the term dependency using traditional statistics corresponding to co-occurrences of terms, thus lacks of an explicit modeling of the Quantum Entanglement (QE), which is a key quantum concept and has a significant cognitive implication.

As a quantummodel, e.g., QLM, it is inconsistent if it cannot express the quantum entanglement in itself. An entangled state can give a more complete description for the nature of global realities, in which the intrinsic correlations among objects are globally determined [Atmanspacher, 2012]. The quantum entanglement is relevant to cognition since it is natural to model the holistic and instantaneous interaction in a cognitive subject [Atmanspacher, 2012]. Technically speaking, a system is entangled, if and only if its state cannot be expressed as a tensor product of its sub-systems. However, in IR practice, it is challenging to measure QE using the classical statistics of texts in a post-measurement configuration, where the state of an object (e.g., the mind of a man) has collapsed to certain observables (e.g., texts).

We resort to the recently proposed Unconditional Pure Dependence (UPD) [Hou et al., 2013] to deal with the abovementioned problem. It is proved that in a post-measurement configuration, the statistical dependence is equivalent to entanglements [Hou and Song, 2009]. In this paper, we reformulate the above statistical dependence as the so-called UPD. Hence we can indeed prove the equivalence relationship between UPD and QE in a post-measurement configuration. Since Hou et al. [2013] have proposed an efficient algorithm to decide, in a sufficient sense, whether a set of variables is UPD, it turns out that we can characterize QE by extracting the UPD patterns from textual datasets.

Moreover, Hou et al. [2013] emphasized that a UPD pattern is not formed by accidental co-occurrences of the words in the sense that its joint distribution cannot be unconditionally factorized. This is coincident with what Ludwig Wittgenstein said: "For a large class of cases of the employment of the word 'meaning' . . . . . . the meaning of a word is its use in the language" [Wittgenstein, 1953]. Wittgenstein defined the word's meaning as the use of the word. Here, the "use" can be characterized by the relationship of the non-accidental co-occurrences of words to a large extent. Since the nonaccidental co-occurrence relationship can be characterized by UPD, which is different from the dependence modeled by QLM, those UPD patterns can further help QLM to model meaningful patterns of words, unlike the unprincipled setting in QLM where accidental co-occurrences of terms are also considered. Through integrating UPD into the QLM's training algorithm, QLM thus naturally takes into account QE, leading to a more consistent quantum IR model.

The rest of this paper is laid out as follows. We first introduce the preliminaries of QT in Section 2. In Section 3, we discuss QE. Then we illustrate the relationship between QE and UPD in Section 4, where we also provide the equivalence proof between QE and UPD for the sake of understandability. We propose to advance QLM with UPD in Section 5. In Section 6, we present the experimental results of our model. Section 7 concludes this work and points out future research directions.

2 Preliminaries of QuantumTheory

In quantum theory [Nielsen and Chuang, 2010], a probabilistic space is defined as a Hilbert space Hn , which is an abstract vector space possessing the structure of the inner product. For convenience, we restrict ourselves to a real space Rn . With the Dirac's notation, a unit column vector ϕ ∈ Rn corresponding to a quantum state can be expressed as the ket |ϕ〉 and its transpose ϕT is the bra 〈ϕ|. The inner product of ϕ and φ is expressed as 〈ϕ|φ〉. Onto the direction |ϕ〉, the corresponding measurement projector is |ϕ〉〈ϕ| = ϕϕT . |ϕ〉〈ϕ| can also represent a quantum state, and hence becomes the density matrix. According to the measurement postulate, the expectation value of the measurement on a density matrix ρ can be calculated by E(H) = ∑m mp(m) = tr(ρH),

where H is a measurement Hermitian with a spectral decomposition. That is, H is equal to its own conjugate transpose and H = ∑m mHm, where Hm is the projector onto the

eigenspace of H with eigenvalue m. In this paper, H is simply defined as a single projector (See Formula (6)). It turns out that tr(ρH) gives the probability that the measurement result corresponding to this projector occurs. All these probability terms can form a quantum probability measure on all possible projectors since Gleason's Theorem [Gleason, 1957] proves a bijective relationship between the density matrix ρ and the quantum probability measure µ, which is determined by µρ(|ϕ〉〈ϕ|) = tr(ρ|ϕ〉〈ϕ|).

3 QuantumEntanglement and Its Cognitive Implications

In quantum theory, a qubit can be completely described by a state vector. Importantly, a qubit can be in a superposition state, i.e., a|0〉 + b|1〉, where |a|2 + |b|2 = 1. The special states |0〉 and |1〉 forming an orthonomal basis are computational basis states. When a qubit is be measured, the superposition state will collapse into one of the base states with certain probability, i.e., the squared norm of the corresponding coefficient of the base. Specially, the entangled state is a special case of the superposition state involving multiple qubits.

The Quantum Entanglement (QE) can be formally defined as follows:

Definition 1. (QE): Let A be an n-qubit system in a state |φA〉 and {A1,A2} be a partition of A, where two disjoint parts A1 and A2 have 0 < k < n qubits and n - k qubits, respectively. A is entangled iff. there does NOT exist any tensor product decomposition of |φA〉 such that |φA〉 = |φA1 〉 ⊗ |φA2 〉, where |φA1 〉 and |φA2 〉 are the states of A1 and A2, respectively.

As an illumination of quantum entanglement, we give an example here. Suppose a state with two qubits is written as √1/2(|00〉 + |11〉), which is the well-known Bell entangled state, also called the EPR pair [Rieffel and Polak, 2000]. From the perspective of the quantummeasurement, it is obvious that any qubit in EPR pair will be completely determined by the measurement result of the other qubit in this pair.

In the following, we describe the cognitive implications of quantum entanglement from its philosophical background and a specific example, i.e., the surprise examination paradox [Chow, 1998; Kritchman and Raz, 2010]. From a philosophical point of view, Pauli and Jung made an analogy that "the change from the unconscious state to a conscious state can be seen as the converting from an entangled state of a system to a measured state" [Atmanspacher, 2012]. They argued that the recognition of the unconscious state is akin to the quantum measurement on the entangled state. Atmanspacher [2012] stated that "measurements can be viewed as an intervention decomposing a system constituting an inseparable whole into locally separate parts". Therefore, in the light of measurement results, we may speculate the knowledge about the holistic state before the measurement.

As we usually directly get the sematic knowledge from texts or propositions in our life, we develop the idea of Pauli and Jung as illustrated in Figure 1. That is, the consciousness, such as the mind and the meaning, is mostly manifested in the form of texts or propositions by thinking logically. After the quantum-like measurement, the consciousness collapses to texts or propositions, which we observe in reality. As illuminated by the above analogies, we can conclude that the conversion of a meaning system from an entangled state to a measured state corresponds with the transformation of a meaning system from a global and implicit state to a local and explicit state due to measurements. Here the measurement results are often texts or propositions.

To further clarify the meaning of the quantum entanglement, we turn to discuss a notable paradox, namely the surprise examination paradox. Here, we give a simplified version: a teacher says to students that there will be an examination in the class on Monday or Wednesday next week and you will not infer the specific date for the examination. If the teacher's claims are formulated under the framework of the Classical Propositional Logic (CPL) system, it can deduce a contradiction. But interestingly, the paradox happens since the examination could be actually held in a class and no student knows the specific date before it happens, which indeed meets the teacher's claims.

This reminds us of Wittgenstein's statement: there are truths of silence, when spoken, no longer true anymore [Wittgenstein, 1961]. Following Wittgenstein's point, the phenomenon of the examination paradox can be understood intuitively. That is, once compatible facts are formalized as propositions and regarded as the premises of the reasoning in the CPL system, conflicts may happen. Actually, G¨odel's second incompleteness theorem [G¨odel, 1931] theoretically explains this phenomenon. That is, the system explicitly introduces a meta proposition on the unprovability of the system, which claims that students cannot infer the specific date for the examination, so that the consistency of the system is broken. We note that the above observations can also be understood under the framework of quantum theory. Specifically, in quantum cognition, there exist holistic truths in the form of entangled states, which cannot be explicitly expressed by propositions or texts. The way to express these holistic truths in a (formal or natural) language can be viewed as the quantum measurement. Although the results of quantum measurements locally reflect holistic truths, a localization (i.e., explicit expressions via propositions or texts) may break the consistency of the expression system.

The examination paradox reveals the limitations of the CPL system. It is thus necessary to seek for a formal and replaceable system to describe the states of entangled objects. In quantum theory, the examination paradox can be simply and completely described with two entangled qubits. Formally, for the first qubit, 0 and 1 represent the examination is held on Monday or Wednesday, respectively. For the second qubit, 0 and 1 represent the students cannot or can infer the specific date for the examination, respectively. Now, the student's cognitive state before the examination can be modeled as a|00〉 + b|11〉, an entangled state, where |a|2 + |b|2 = 1. The class on Monday can be seen as a measurement on the first qubit, which makes the resulting state become localized propositions. Specifically, if the examination is on Monday, the entangled state collapses to |00〉, which means that the examination is held on Monday and students cannot infer the date for the examination. Otherwise, the student's cognitive state collapses to |11〉. No matter what the outcome is, the student's cognitive state changes substantially owing to the quantum measurement. This is in sharp contrast with the CPL system, in which the procedures of the reasoning do not produce any new knowledge in nature, since all logical conclusions are actually implied by the logical premises. Therefore, the state of the CPL system is essentially static. On the other hand, the quantum state can characterize not only whether the proposition comes into being or not, but also the probability of the occurrence of the proposition in principle. In this sense, the quantum state may give a more complete description than the CPL system. Main differences between the formalizations of the CPL and the quantum state representation are listed in Table 1.

The above analysis indicates that the quantum state may be more useful and powerful than the CPL system in some contexts. In particular, the quantum entanglement reflects the intrinsic correlations among the potential propositions we concern about. It is these correlations that globally determine the whole student's cognitive state and the state collapsing induced by measurements. Furthermore, a quantum state may also evolve in accordance with the unitary matrix. Therefore, we can define the QT model as a model that describes the states of objects by, in general, entangled state vectors, and characterizes the localization and evolution of the states by quantum measurements and unitary evolutions, respectively. It is worth emphasizing that, in this framework, the quantum entanglement is a key component since it rules the holistic behaviors of the quantum state.

In IR, our task is to retrieve documents that are relevant to a query topic. The underlying meaning of a document globally determine which topic it belongs to. To a large extent, we can capture the underlying meaning through the high-level meaningful entities/blocks. It is natural that this kind of entities is constituted by a set of intrinsically correlated components in an entangled (meaning) state. In a post-measurement configuration, in which the meaning is fixed by the measurement results, i.e., texts, an entangled state manifests itself as the special statistical dependence among words (see Section 4 for details). For example, a text pattern "Seattle World fair", in which the words are significantly dependent, implies the whole concept of "world's fair in Seattle", i.e., a high-level meaningful entity. As a conclusion, it is important to characterize the quantum entanglement in an IR model.

4 The Relationship between QE and UPD

We expect to model QE in QLM. However, it is usually impossible for us to directly measure a quantum-like system, e.g., the mind of a man, where the quantum measurement occurs in the generation process of texts. In common applications, we have only these texts or statistical data, which correspond to the measurement results of the underlying quantumlike system. While, the statistics of texts comply with classical logic and probability, which are incompatible with pure quantum approaches. Hence we need a criterion to decide the existence of quantum entanglement from the measurement results of a quantum system. To this end, Hou and Song [2009] described that the entanglement corresponds to the statistical dependence between measurement results. In the following, we reformulate the above statistical dependence as the unconditional pure dependence. Hence we can indeed prove the equivalence relationship between the unconditional pure dependence and the quantum entanglement in a postmeasurement configuration.

In a post-measurement configuration, the counterpart of QE is Unconditional Pure Dependence (UPD) defined as below. Formally, given a set of binary random variables, A = {W1,W2, · · · ,Wn}, where Wi denotes the occurrence (Wi = 1) or absence (Wi = 0) of the ith word. Let wi ∈ {0, 1} stand for the value of Wi and p(a), a = [w1, w2, · · · wn]T be the joint distribution over A. Then we have:

Definition 2. (UPD): A pattern A = {W1,W2, · · · ,Wn} forms the UPD pattern iff. the joint probability distribution over A cannot be unconditionally factorized, i.e., there does NOT exist any m-partition {A1,A2, · · · ,Am;m > 1} of A, so that p(a) = p(a1) · p(a2) · · · p(am), where p(ai), i = 1, 2, · · · ,m, is the joint distribution over Ai.

Based on Definition 1 and Definition 2, a set of objects in an entangled system or a UPD pattern are both recognized as a whole, which cannot be decomposed by the individual counterparts in the sense that the states of any part are intrinsically correlated with the states of the rest. This intuitive similarity between QE and UPD implies a possible logical connection between them. In the following, we will formally clarify this connection.

To uncover the relation between QE and UPD, we first define the characterizing distribution of a quantum state. Given a quantum state |φ〉, the characterizing distribution of |φ〉 is the (classical) joint probability distribution indicating the occurrence probability of all possible measurement results on all qubits of |φ〉. For example, if |φ〉 = √1/2(|00〉 + |11〉), then the characterizing distribution of |φ〉 is just a discrete joint distribution with p00 = 1/2, p01 = 0, p10 = 0 and p11 = 1/2.

Proposition 1. Let A be an n-qubit system in a state |φA〉. A is entangled iff. the characterizing distribution of |φA〉 is unconditional pure dependent.

Proof. To prove the sufficiency, we assume that A is not entangled, i.e., |φA〉 has a tensor product composition |φA〉 = |φA1 〉 ⊗ |φA2 〉, where |φA1 〉 and |φA2 〉 corresponds to the states of two disjoint parts of A, i.e., A1 and A2, respectively. Note that {A1, A2} should be a partition of A. Without loss of generality, we suppose that |φA1 〉 includes the first k qubits of |φA〉 and |φA2 〉 includes the last (n - k) qubits of |φA〉 . Denote |φA〉 = z0···0|0 · · · 0〉 + · · · + z1···1|1 · · · 1〉, |φA1 〉 = x0···0|0 · · · 0〉 + · · · + x1···1|1 · · · 1〉 and |φA2 〉 = y0···0|0 · · · 0〉 + · · · + y1···1|1 · · · 1〉. Note that the dimensionalities of |φA〉, |φA1 〉 and |φA2 〉 are different. Substitute these representations into the tensor product composition of |φA〉, it is easy to check that the following relations holds:

for any i1 · · · in, where ∀ij ∈ {0, 1} . The Formula (1) exactly implies that the characterizing distribution of |φA〉 is not unconditional pure dependent. The sufficiency follows.

To prove the necessity, we assume that the characterizing distribution of |φA〉 is not unconditional pure dependent. That is, the characterizing distribution of |φA〉 has a factorization. It is easy to check that a factorization of the characterizing distribution of |φA〉 entails a tensor product composition of |φA〉 as depicted in Formula (1). It turns out that the |φA〉 is not entangled. The necessity follows.

Based on Proposition 1, QE is equivalent to UPD in a postmeasurement configuration. Hence we can decide the existence of QE via UPD, and furthermore use the measure of UPD as a quantitative index of QE.

5 AQuantum IRmodel with Quantum Entanglements

Quantum Language Model (QLM) is a recently proposed quantum-like method to retrieve documents given query topics. To make QLM with more quantum properties, we propose to enhance QLM by characterizing the quantum entanglement in QLM. Based on Proposition 1, the issue of characterizing the quantum entanglement converts to identify the UPD patterns from texts. Since deciding the UPD is NPhard in general, Hou [2013] developed a UPD pattern extraction method based on Information Geometry (IG), which can efficiently decide the UPD in a sufficient sense. With this method, an enriched Quantum IR model with Quantum Entanglements (QQE) can be naturally realized.

Similar to QLM, we represent documents by a series of projectors. However, the way to build projectors is different from the original QLM since we use a different procedure to choose dependence patterns, which thereby results in different actual representations of documents and queries. In our QQE model, the procedures of building the sequence of projectors for the document are as follows.

Firstly, for a specific query, we extract UPD patterns using a Log Likelihood Ratio Test (LLRT), which is designed under a principled IG framework [Hou et al., 2013]. The testing statistic ρ [Nakahara and Amari, 2002] of LLRT is derived as follows:

where N is the sample numbers, the values of gdd and θcoordinate can be calculated by the method given in [Hou et al., 2013]. The degree that a pattern is unconditional pure dependent in terms of the statistic ρ of LLRT is estimated by the confidence level π.π = cdfχ2 (1)(ρ), (3)

where cdf denotes the cumulative distribution function of χ2 (1). For instance, given a query Q with n words, Q = {wj; j = 1, · · · , n} and a pattern {w1,w2} with computed ρ=5.024, we can guarantee that this pattern is a UPD pattern with probability 0.95. For more details of the extracting method, please refer to Section 5 in [Hou et al., 2013].

Secondly, we represent uni-terms and UPD patterns as projectors based on the method proposed in [Sordoni et al., 2013]. For the query Q, suppose the set {|ewj 〉} forms an orthonormal basis. The projector for a uni-termwj is below:

The projector for a UPD pattern K = {wi; i = 1, · · · , h} is as follows:

where σi can be assigned to the uniform (σi = √1/n) weight or the normalized inverse document frequency (idf) weight.

Thirdly, for each occurrence of uni-terms and UPD patterns in unordered fixed windows (with length L) of a document, we add their projectors to the sequence of projectors for the document. Specifically, we design Algorithm 1 to build the sequence of projectors for a document D. Note that #uwL(wj,D) or #uwL(K,D) is an Indri expression which returns the occurrence times of wj or K in unordered windows (with length L) of D.

Algorithm 1 Build the sequence of projectors SD for D.

Require: Q = {wj; j = 1, · · · , n}; D; U: the UPD patterns

for Q. 1: Initialize SD ← ∅; 2: for each wj in Q do 3: for i = 1 to #uwL(wj , D) do 4: add m(wj) to SD; 5: end for 6: end for 7: for each pattern K in the power set P(Q) -{∅} do 8: if K ⊂ U then 9: for i = 1 to #uwL(K, D) do 10: add m(K) to SD; 11: end for 12: end if 13: end for 14: return SD

After obtaining the sequence of projectors for documents, we follow the same training method as QLM [Sordoni et al., 2013] to estimate density matrices. Specifically, given a sequence of projectors SD = m1, · · · ,mN for a document D, in QLM, density matrices are estimated by:

The RρR algorithm [Lvovsky, 2004] is used for solving the above maximization problem. The Dirichlet smoothing method is used to smooth the density matrices. In Formula (6), the projectors consist of the mappings of uni-terms and UPD patterns. This is different from QLM, in which the uniterms and all possible combinations of uni-terms are modeled as projectors. In this sense, our model can reduce the time complexity when we train the density matrix.

Finally, the negative quantum relative entropy of the query density matrix ρQ to the document density matrix ρD is considered as the scoring function:

6 Experimental Results and Analyses

To verify the effectiveness of our model, we conduct experiments on five collections in the documents re-ranking task. Table 2 describes the collections in detail. Only the title queries are considered in the experiments. The collections have been stemmed with the Porter stemmer and processed with the standard stop word list when using the Lemur 4.12 for building index. For all the models, we apply the Dirichlet smoothing method [Zhai, 2008] in which the parameter µ is set to be a typical value 2500. A pool of N(N=80,100) documents retrieved by the unigrammodel is used for re-ranking, while we obtain similar observations for other N's settings. Mean Average Precision (MAP) is adopted as the metric to evaluate the retrieval performance. We ignore the queries whose relevant documents are not given in the standard results. The Student's test is used as the statistical significance test method, where the level is 0.05. The unconditional pure dependence patterns with at most three orders are taken into account, in order to reduce the computational cost. The length of the unordered fixed window in Algorithm 1 is set to be: L = 4 · |K|, where |K| is the numbers of terms appearing in the UPD pattern K [Metzler and Croft, 2005].

6.1 Our Model (QQE) vs. QLM

As discussed previously, a main advantage of our model QQE described in Section 5 over the original QLM is that QQE characterizes the quantum entanglement by retaining UPD patterns while removing non-UPD ones in choosing projectors of QLM. We report the experimental results in Table 3.

From Table 3, we can see that our model achieves stable improvements over QLM on all the five collections. From the results of the statistical significant test, QQE is significantly effective on FR, ZIFF and SJM collections, in comparison with QLM. We then investigate the lengths of queries in these collections. An observation is that QQE is more effective for the relatively long queries. This is possibly because that there are more possible combinations of uni-terms as dependence patterns for the longer query in the original QLM, but some dependence patterns (especially the non-UPD ones) could introduce noises and may be irrelevant to certain queries. Different weight parameters σi (the uniform weight or the idf weight) in Formula (5) also influence the retrieval performance. The results show that QQE idf outperforms QQE uni slightly on FR, DOE and WT10G collections. It indicates that idf weights seem to be more reasonable than uniform weights.

6.2 Our Model (QQE) vs. MRF T UPD

The Markov Random Field (MRF) retrieval model [Metzler and Croft, 2005] makes use of three features, i.e., uni-terms, sequential terms and unordered terms. The UPD [Hou et al., 2013] was once adopted in the MRF model, for the purpose of refining the sets of sequential terms and unordered terms. Therefore, it is necessary to compare the performance of UPD patterns used in the traditional retrieval model (e.g., MRF)

and the quantum retrieval model (e.g., QLM), respectively. In order for a fair comparison, we only use UPD to refine the sets of unordered terms. In our experiments, the unigram model [Song and Croft, 1999] and the MRF T U model are involved. The capital T, U and UPD represent that the model uses uni-terms, unordered terms (#uw) and UPD patterns, respectively. The detailed results are presented in Table 4.

Table 4 shows that QQE outperforms the unigram model substantially in the five collections. In comparison with MRF T UPD, QQE still achieves better performances. Particularly, MRF T UPD is slightly worse than MRF T U on ZIFF collection, but QQE idf achieves larger improvements over MRF T U on this collection. These results indicates that it seems to be more useful to apply UPD patterns in a quantum IR model (e.g., QLM). This is possibly because the UPD patterns, which have proved connections with the quantum entanglements, can be naturally modeled in building projectors in QLM.

In summary, two groups of experiments show similar observations on the effectiveness of the proposed QQE. Specifically, the results show that QQE achieves better performances than QLM (a quantum IR model) and MRF T UPD model (a traditional IR model with UPD patterns).

7 Conclusions and FutureWorks

In this paper, we introduce the quantum entanglement in the field of information retrieval. In order to measure and decide QE, we theoretically prove the equivalence between QE and UPD in a post-measurement configuration. This help us infer the occurrence of QE by extracting UPD patterns. We then enhance a Quantum IR model (i.e., QLM) with Quantum Entanglements (QQE) by reserving the UPD patterns in building projectors in QLM. The experimental results show that our model QQE is more effective than the quantum language model and a traditional IR model namely MRF.

Our future work will be focused on analysing the proposed methodology and specific models on some other IR/NLP tasks (e.g., the session search) and investigating the resulted new problems and observations. We will also analyse how to effectively set the value of σi (in Formula 5) in a more principled manner. Furthermore, we will develop some other effective representations for documents and queries, using the concept of QE and UPD.

Acknowledgments

This work is funded in part by the Chinese 863 Program (grant No. 2015AA015403), the Chinese 973 Program (grant No. 2013CB329304 and 2014CB744604), the Chinese NSF Project (grant No. 61272291, 61402324 and 61272265), the Key NSF Project of Chinese Tianjin (grant No. 15JCZDJC31100) and the Major Project of Chinese National Social Science Fund (grant No. 14ZDB153).