Sampling quantum nonlocal correlations with high probability

arXiv:1412.4010v1 [quant-ph] 12 Dec 2014 SAMPLING QUANTUM NONLOCAL CORRELATIONS WITH HIGH PROBABILITY C. E. GONZ´ ALEZ-GUILL´ EN, C. H. JIM´ ENEZ, C. PALAZUELOS, AND I. VILLANUEVA Abstract. It is well known that quantum correlations for bipartite dichotomic measurements are those of the form γ= (hui, vji)n i,j=1 , where the vectors ui and vjare in the unit ball of a real Hilbert space. In this work we study the probability of the nonlocal nature of these correlations as a function of α=m n, where the previous vectors are sampled according to the Haar measure in the unit sphere of Rm. In particular, we prove the existence of an α0>0 such that if α≤α0,γis nonlocal with probability tending to 1 as n→ ∞, while for α > 2, γis local with probability tending to 1 as n→ ∞. Introduction It is well known that local measurements on entangled bipartite quantum states can lead to correlations which cannot be explained by Local Hidden Variable Models (LHVM) [7]. This phenomenon, known as quantum nonlocality, is one of the most relevant features of quantum mechanics. In fact, though initially discovered in the context of foundations of quantum mechanics, during the last decade quantum nonlocality has become a crucial resource in many applications; some of them are quantum cryptography ([1], [2], [15]), communication complexity ([8]) and random number generators ([14], [16]). In this work, we will consider a particularly simple but very interesting context, where two spatially separated observers, Alice and Bob, perform dichotomic (two-outcome) measurements on a bipartite quantum state ρ, each on their part of the system. The simplicity of this scenario has made it the natural one to start developing the previously mentioned applications and also in the experimental verification of the quantum nonlocality phenomenon (see for instance [4], [5]). According to the postulates of quantum mechanics, a two-outcome measurement for Alice (resp. Bob) is given by {A+, A−}(resp. {B+, B−}), where A±(resp. B±) are projectors acting on a Hilbert space and summing to the identity. We define the observable corresponding to Alice’s (Bob’s) measurement as A=A+−A− (B=B+−B−). The joint correlation of Alice’s and Bob’s measurement results, denoted by aand brespectively, is habi=tr(A⊗Bρ). Motivated by this, we say that γ= (γi,j)n i,j=1 is a quantum correlation matrix and denote by γ∈ Q, if there 1 2 C. E. GONZ ´ ALEZ-GUILL´ EN, C. H. JIM´ ENEZ, C. PALAZUELOS, AND I. VILLANUEVA exist a density matrix1ρacting on a tensor product of Hilbert spaces H1⊗H2 and two families of contractive self-adjoint operators {Ai}n i=1,{Bi}n i=1 acting on H1and H2respectively such that γi,j =tr(Ai⊗Bjρ) for every i, j = 1,···, n.(0.1) That is, γis a matrix whose entries are the correlations obtained in an AliceBob scenario where each of the observers can choose among ndifferent possible dichotomic measurements. On the other hand, we say that γ= (γi,j)n i,j=1 is a local correlation matrix if it belongs to the convex hull L=convn(αiβj)n i,j=1, αi=±1, βj=±1, i, j = 1,···, no.(0.2) Local correlation matrices are precisely those whose entries are the correlations obtained in an Alice-Bob scenario when the measurement procedure can be explained by means of a LHVM. It is well known ([17]) that Land Qare convex sets satisfying L Q KGL, where 1.67696... ≤KG≤1.78221... is the so called Grothendieck’s constant2. Indeed, the first strict inclusion exactly means that there exist quantum correlations which cannot be explained by means of a LHVM (what we have called quantum nonlocality above) while the second inclusion is a consequence of Grothendieck’s inequality (see Theorem 1.4 below) and a result proved by Tsirelson ([17]) which states that γ= (γi,j)n i,j=1 is a quantum correlation matrix if and only if there exist a real Hilbert space Hand unit vectors u1,···, un, v1,···, vnin Hsuch that γi,j =hui, vjifor every i, j = 1,···, n.(0.3) As we just mentioned, we know of the existence of quantum correlations which are nonlocal. A natural question appears now: how common is nonlocality among quantum correlations? That is, if we pick “randomly” a quantum correlation, which is the probability that it is nonlocal? To study this problem, we first need to choose a probability distribution on the set of quantum correlations, in other words, a way of sampling these matrices. We see at least two natural candidates for this. At first sight, it would seem from expression (0.1) that a natural procedure would be sampling on the set of states ρand on the set of families of self-adjoint and contractive operators A1,···, An, B1,···, Bn. The problem with this approach is twofold. First, we do not know a natural probability measure on the set of selfadjoint contractive operators. Second, it seems that we would need to allow for Hilbert spaces of very high dimension3. 1A density matrix is a positive operator ρ:H→Hacting on a Hilbert space Hwith tr(ρ) = 1. 2The exact value of the Grothendieck’s constant is still unknown. 3It is known ([17]) that every quantum correlation γ= (γi,j )n i,j=1 can be written as in (0.1) by using a Hilbert space of dimension exponential in nand, furthermore, such a dimension is required in order to describe the extreme points of Q. SAMPLING QUANTUM NONLOCAL CORRELATIONS WITH HIGH PROBABILITY 3 So, we look for the second candidate: looking at the equivalent reformulation (0.3) of a quantum correlation, we do have a natural sampling procedure: we can sample the vectors u1,···, un, v1,···, vnindependently uniformly distributed on the unit sphere of Rm. It is well known that this is exactly the same as sampling independent normalized m-dimensional gaussian vectors. Our results will depend on the relation between the dimension mand the number of questions n. As we will show later, it is very easy to see that if one fixes any finite m, the probability that a quantum correlation matrix sampled according to the previous procedure is nonlocal tends to one as ntends to infinity. However, this kind of sampling, though interesting to obtain quantum nonlocal correlations, does not say much about our problem, since the set of quantum correlation matrices of order nwhich can be obtained with a fixed mis very small. We are interested in the case where mand nare of the same order. In that case we are sampling on a representative set of quantum correlation matrices. The main result of our work can be condensed as: Theorem 0.1. Let nand mbe two natural numbers and α=m n. Let us consider 2n vectors u1,···, un, v1,···, vnsampled independently according to the Haar measure on the unit sphere of Rmand let us denote by γ= (hui, vji)n i,j=1 the corresponding quantum correlation matrix. a) If α≤α0≈0.004 then γis nonlocal with probability tending to one as n tends to infinity. b) If α > 2, then γis local with probability tending to one as ntends to infinity. This result shows clearly the need of studying the problem as a function of the parameter α=m n. One possible way to think of this problem is the following: say that we want to sample our vectors on a space of large dimension m. In that case, how many vectors u1,···, un, v1,···, vnwill we need to sample in order to have nonlocality with high probability? Our results show that n=m 2will be too few vectors, whereas n=m α0will be enough. There is a considerable gap between α0and 2. Our techniques could be refined to slightly increase the bound α0, but they will never reach the relevant case α0= 1. From the other side, our proof of part b) suggests that a more clever argument could lead to replace 2 by KG, but again our present approach does not seem to allow for further improvement. Along these lines, it is plausible that a relation between αand KGdescribes interesting behaviors of our correlation matrices. It would be very interesting to understand the problem for the values α∈ (α0,2) both by reducing this gap and by studying the existence, or not, of a sharp threshold behaviour of the probability of nonlocality. 4 C. E. GONZ ´ ALEZ-GUILL´ EN, C. H. JIM´ ENEZ, C. PALAZUELOS, AND I. VILLANUEVA Interestingly enough, we will see below that if one samples normalized vectors whose entries are independent Bernoulli variables, the probability of obtaining a nonlocal correlation matrix is zero, since all of them will be local. This means that, in contrast to many other contexts in random matrix theory, sampling gaussian and Bernouilli random variables in our problem leads to completely different conclusions. In order to prove Theorem 0.1 we will use a result previously proved in [10] on random matrix theory. Similar techniques were previously used in [3] in order to study the dual problem; that is, how likely it is for a random (in some sense) XOR game to have a maximum quantum value strictly bigger than a maximum classical value. In that case, the authors studied the values ω∗(A) and ω(A) for random matrices4A= (ai,j)n i,j=1, where ω∗(A) = sup  n X i,j=1 ai,jγi,j :γ∈ Qand ω(A) = sup  n X i,j=1 ai,jγi,j :γ∈ L. They concluded that, for any given ǫ > 0, ω∗(A)≥(2 −ǫ)n3 2and ω(A)≤ 1.6651 . . . n3 2with probability 1 −o(1) as n→ ∞ in both cases. This result is the starting point for the proof of our Theorem 0.1. Note that stating ω∗(A) ω(A)>1 for some A’s is a reformulation (in a quantitive way) of the fact that L Q. The elements A’s are usually called correlation Bell inequalities (or XOR-games in the context of computer science) and the fact that ω∗(A) ω(A)>1 is usually referred to as aBell inequality violation. The paper is organized as follows. In the first section we briefly introduce some basic results which will be used along the whole paper. The proof of Theorem 0.1 is presented in Section 2 and Section 3. The proof of part a) of the theorem, based on some results on random matrix theory, is given in Section 2, while Section 3 deals with the proof of part b). 1. Preliminary results For completeness and to simplify the reading of the paper, we state in this section the known, or essentially known, previous results which we use along the paper. The following proposition can be easily deduced from [11, Lemma 2.2]. Proposition 1.1. Let Gnbe the gaussian measure on Rnand let L⊂Rnbe a k-dimensional subspace. For a vector g= (g1,···, gn)∈Rn, let ¯g=g kgkand let PL(¯g)denote the orthogonal projection of ¯gonto L. Then, for any 0< ρ < 1we 4Although the authors focused on sign matrices, the same proof works in the case of more general random matrices. SAMPLING QUANTUM NONLOCAL CORRELATIONS WITH HIGH PROBABILITY 5 have Gn (g1,···, gn)∈Rn:kPL(¯g)k ≥ 1 1−ρrk n!≤e−ρ2k 4, and Gn (g1,···, gn)∈Rn:kPL(¯g)k ≤ (1 −ρ)rk n!≤e−ρ2k 4. Remark 1.1. As we already mentioned in the Introduction, it is completely equivalent to sample a unit vector u∈Sn−1according to the Haar measure µnto sample normalized gaussian vectors g=1 k(g1,···,gn)k(g1,···, gn). That is, both probability distributions are exactly the same (see [6, Section 3.3] for a more complete explanation). In particular, Theorem 0.1 can be equivalently stated as it is in Theorem 2.3 and Theorem 3.1. Moreover, we can also state the previous proposition in a completely analogous form for unitary vectors and obtain: µn u∈Sn−1:kPL(u)k ≥ 1 1−ρrk n!≤e−ρ2k 4, and µn u∈Sn−1:kPL(u)k ≤ (1 −ρ)rk n!≤e−ρ2k 4. We say that a real random n×nmatrix Mis bi-orthogonally invariant if the distribution on Mn(R) of Mis equal to that of O1MO2for any orthogonal matrices O1and O2. It is well known and easy to check that gaussian matrices are biorthogonally invariant. The following result is probably well known, but we have not found a reference for it. We write a proof, following the ideas of [13, Lemma 4.3.10]. Proposition 1.2. Let A∈Mn(R)be an n×nrandom matrix in some probability space (Ξ,P). If Ais bi-orthogonally invariant then there exist random matrices U and V in (Ξ,P)such that (i) U, V follow the Haar distribution in the orthogonal group O(n). (ii) Uand Vare independent. (iii) Uand Vare the matrices whose columns are respectively the left and right singular vectors associated to the ordered singular values of A. Proof. For simplicity, we will assume that the set of matrices with repeated singular values has zero measure (as it happens in the gaussian case, which is the one we will use here). In this case, the singular value decomposition is unique with probability 6 C. E. GONZ ´ ALEZ-GUILL´ EN, C. H. JIM´ ENEZ, C. PALAZUELOS, AND I. VILLANUEVA one up to the choice of the sign of the right (or left) singular vectors5. Let Abe a random matrix defined in some space (Ξ,P), and let A(ξ) = U(ξ)Σ(ξ)V∗(ξ) be the singular value decomposition of A(ξ) where the singular values of Σ(ξ) are ordered in decreasing order and the sign (of the first non zero coordinate) of the right singular vectors are taken at random with probability 1/2.6 The random matrices Uand Vfulfill (iii) by construction. To prove (i) and (ii) it is enough to show that for any B1, B2⊂ O(n) and ∆ ⊂Mn(R) Borel sets, we have P(U(ξ)∈B1,Σ(ξ)∈∆, V ∗(ξ)∈B2) = µn(B1)P(Σ(ξ)∈∆) µn(B2), where µnis the Haar measure on the orthogonal group. It follows from the biorthogonal invariance of Athat for any two (fixed for now) orthogonal matrices O1and O2, the random matrix A′=O1AO2has the same distribution as A. Defining U′=O1U,V∗′=V∗O2, it is clear that A′=U′∆V∗′ is a singular value decomposition of A′verifying our requirements. Therefore P(U(ξ)∈B1,Σ(ξ)∈∆, V ∗(ξ)∈B2) = P(O1U(ξ)∈B1,Σ(ξ)∈∆, V ∗(ξ)O2∈B2) If we now let O1and O2be distributed according to the Haar measure µnon different probability spaces (Ξ′,P′) and (Ξ′′,P′′) respectively, we get P(U(ξ)∈B1,Σ(ξ)∈∆, V ∗(ξ)∈B2) = (P′⊗P⊗P′′)(U′(ξ, ξ′)∈B1,Σ(ξ)∈∆, V ′∗(ξ, ξ′′)∈B2) =Z Z Z χB1(O1(ξ′)U(ξ))χ∆(Σ(ξ))χB2(V∗(ξ)O2(ξ′′))dP(ξ)dP′(ξ′)dP′′(ξ′′) =ZZχB1(O1(ξ′)U(ξ))dP′(ξ′)χ∆(Σ(ξ)) ZχB2(V∗(ξ)O2(ξ′′))dP′′(ξ′′)dP(ξ) =Zµn(B1)χ∆(Σ(ξ))µn(B2)dP(ξ) =µn(B1)P(Σ(ξ)∈∆)µn(B2), where the fourth equality follows from the rotational invariance of the Haar measure.  Remark 1.2. We will use at several points of the paper the following easy consequence of Proposition 1.2: For every n∈Nthere exists a probability space Ξ 5The general case follows by considering the set Viof right singular vectors associated to the singular value si, and taking random choices of orthonormal vectors Vias the associated columns of the matrix V. The measure in Viis the induced by the Haar measure, that is, the measure invariant under unitary transformations of Viinto itself. 6We see A(ξ) = U(ξ)Σ(ξ)V∗(ξ) with U(ξ) = U0(ξ)S(ζ) and V∗(ξ) = S(ζ)V∗ 0(ξ), where U0(ξ) and V0(ξ) are a particular choice of matrices in the singular value decomposition and S(ζ) is a diagonal random matrix with even iid ±1 Bernoulli entries. SAMPLING QUANTUM NONLOCAL CORRELATIONS WITH HIGH PROBABILITY 7 with three n×nrandom matrices A, U, V defined on it such that Ais a gaussian matrix, U, V are independent and Haar distributed in O(n), and for almost every ξ∈Ξ, U(ξ) and V(ξ) are the right and left singular values of A(ξ) arranged in decreasing order of the singular values. We will need the Marcenko-Pastur law, describing the distribution of the singular values of random matrices: Theorem 1.3 (Marcenko-Pastur law, [12]).Let Abe an n×nrandom matrix whose entries aij are independent real random variables with mean 0and variance 1. Let C∈[0,2]. With probability 1−o(1), the number of singular values λof A that satisfy λ≥C√nis (f(C)−o(1))nwhere f(C) = 1 2πZ4 x=C2r4 x−1dx. Here, we say that h=h(n)is o(1) if and only if limn→∞ h(n) = 0. Finally, we state for completeness the version of Grothendieck’s inequality most useful for our purposes (see [9, Page 172]). Theorem 1.4 (Grothendieck’s inequality).There exists a universal constant KG, such that for every natural number nand for every real matrix (ai,j)n i,j=1 we have sup n n X i,j=1 ai,jhxi, yji:xi, yj∈BHo≤KGsup n n X i,j=1 ai,jsitj:si, tj=±1o, where the first supremum runs over elements x1,···, xn, y1,···, ynin the unit ball of a real Hilbert space H. The exact value of KGis still unknown but we have 1.67696... ≤KG≤1.78221.... 2. A lower bound for α0: Part a) of Theorem 0.1 The following result is implicit in the paper [3]. It provides an abundance of quantum nonclassical correlations and it is the starting point of our work. Proposition 2.1. Let U= (ui,j)n i,j=1, V = (vi,j)n i,j=1 be two independent orthogonal random matrices distributed according to the Haar measure on the orthogonal group O(n). Let α∈(0,1) and m=αn. We also denote δ=f−1(α), where fis the Marcenko-Pastur densitiy function as in Theorem 1.3. Let γi,j =h√n √mui,√n √mvji with ui= (ui,k)m k=1 vj= (vj,k)m k=1. Then there exists an n×nmatrix A= (ai,j)n i,j=1 such that, with probability 1−o(1), n X i,j=1 ai,jγi,j ≥(δ−o(1))n3 2and ω(A)≤1.6651 . . . n3 2. 8 C. E. GONZ ´ ALEZ-GUILL´ EN, C. H. JIM´ ENEZ, C. PALAZUELOS, AND I. VILLANUEVA Proof. We consider A, U, V distributed as in Remark 1.2. So, A=UΣV∗, with Σ is the diagonal matrix of the singular values which we may asume arranged in decreasing order. Let λ1, ..., λmbe the greatest msingular values of A. According to our choice of δ, it follows from Theorem 1.3 that λm≥(δ−o(1))√nwith probability 1 −o(1). Then, we have n X i,j=1 ai,j√n √mui,√n √mvj=n m n X i,j=1 ai,jhui, vji=n m m X k=1 λk≥(δ−o(1))n3 2. This proves the first inequality of our statement. For the second one, note that Ais a gaussian matrix. Then the result follows exactly as in [3, Theorem 5] from the Chernoff bound: Pr n X k=1 akXk≥t≤2e−t2 2kak2, where Xkare normalized real gaussian variables and a= (a1, ..., an)∈Rn, taking t=2√ln 2 + 2√ln n √nn3/2and applying a union bound argument.  Now we can state and prove the first part of Theorem 0.1. It states that most correlations will be nonlocal when mis of the order α0n. The idea of the proof is the following: Proposition 2.1 shows that for that order of mthe first mrows/columns of two Haar distributed orthogonal matrices generate a nonlocal quantum correlation. It also provides a gaussian matrix Athat certifies this nonlocality. On the other hand, the following theorem shows that the first mcolumns of a gaussian matrix are “close”, in an appropriate sup-euclidean norm, to the first mcolumns of a Haar distributed orthogonal matrix. Theorem 2.2. [10, Theorem 1.1] Let nand mbe two natural numbers such that α=m n∈(0,1). Then, there exist matrices Yn= (yi,j)n i,j=1 and Un= (uij)n i,j=1 whose 2n2entries are real random variables defined on the same probability space Ξsuch that (i) {yi,j; 1 ≤i, j ≤n}are independent normalized random gaussian variables, (ii) Unis an orthogonal matrix distributed according to the Haar measure, (iii) If we set Fm i(Yn−√nUn)the i-th row of the matrix Yn−√nUntruncated to its first mentries, we have PΞsup i=1,···,n  Fm i(Yn−√nUn) >(1 + ǫ)θ(α)√m≤KneC(ǫ,α)n, where here Kis a universal positive constant, C(ǫ, α)>0is a constant depending only on ǫand αand θ(α) = r2−4 3 (1 −(1 −α)3/2) α. SAMPLING QUANTUM NONLOCAL CORRELATIONS WITH HIGH PROBABILITY 9 Finally, Grothendieck’s inequality allows us to translate this sup-euclidean closeness into a big value of the correlation γwhen tested against the witness A. Theorem 2.3. Let G= (gi,j)n,m i,j=1 and H= (hi,j)n,m i,j=1 be two random matrices whose entries are independent real normalized gaussian variables satisfying α= m n∈(0,1). For every i, j = 1,···, n, let gi= (gi,k)m k=1 and hj= (hj,k)m k=1 be the row vectors of Gand Hrespectively . Let us denote ¯gi=gi kgikand ¯ hj=hj khjk. Then, if α≤α0≈0.004, the quantum correlation matrix given by γ= (h¯gi|¯ hji)n i,j=1is not local with probability 1−o(1). As we will explain below, it suffices to show the result for α=α0. Proof. Following Remark 1.2 and Theorem 2.2 we may consider Aa gaussian matrix, Uand Vthe matrices formed by the left and right singular vectors of A, arranged in decreasing order, and G′and H′the independent gaussian matrices whose Gram-Schmidt orthonormalization yields Uand Vrespectively. Now, G and Hfrom the statement are the first m columns of matrices G′and H′7. Let us denote by G2n2the gaussian measure of dimension 2n2. We define ui= (ui,k)m k=1 and vj= (vj,k)m k=1. According to Proposition 2.1 we have (2.1) ω(A)≤1.6651 . . .n3 2 with probability 1 −o(1). We need to see now that Pn i,j=1 ai,jγi,j is greater than this value. We write ¯gi=√nui √m+gi √m−√nui √m+ ¯gi−gi √m:= √nui √m+εi, ¯ hj=√nvj √m+hj √m−√nvj √m+¯ hj−hj √m:= √nvj √m+σj. Therefore, Pn i,j=1 ai,jγi,j=Pn i,j=1 ai,jh¯gi,¯ hjiis lower bounded by  n X i,j=1 ai,j√nui √m,√nvj √m− n X i,j=1 ai,j√nui √m, σj (2.2) − n X i,j=1 ai,jεi,√nvj √m− n X i,j=1 ai,jεi, σj. 7Note that the last n−mcolumns of G′and H′will not play any role in the proof. They are only introduced in order to apply Theorem 2.2 in a simple way.