Full text

Turn on search term navigation

ARTICLE

Received 8 Nov 2012 | Accepted 8 Jul 2013 | Published 16 Aug 2013

In recent years, the use of information principles to understand quantum correlations has been very successful. Unfortunately, all principles considered so far have a bipartite formulation, but intrinsically multipartite principles, yet to be discovered, are necessary for reproducing quantum correlations. Here we introduce local orthogonality, an intrinsically multipartite principle stating that events involving different outcomes of the same local measurement must be exclusive or orthogonal. We prove that it is equivalent to no-signalling in the bipartite scenario but more restrictive for more than two parties. By exploiting this non-equivalence, it is then demonstrated that some bipartite supra-quantum correlations do violate the local orthogonality when distributed among several parties. Finally, we show how its multipartite character allows revealing the non-quantumness of correlations for which any bipartite principle fails. We believe that local orthogonality is a crucial ingredient for understanding no-signalling and quantum correlations.

DOI: 10.1038/ncomms3263

Local orthogonality as a multipartite principle for quantum correlations

T. Fritz1,2, A.B. Sainz1, R. Augusiak1, J. Bohr Brask1, R. Chaves1,3, A. Leverrier1,4,5 & A. Acn1,6

1 ICFOInstitut de Ciencies Fotoniques, Castelldefels, Barcelona E08860, Spain. 2 Perimeter Institute for Theoretical Physics, Waterloo, Ontario, Canada.

3 Institute for Physics, University of Freiburg, D-79104 Freiburg, Germany. 4 Institute for Theoretical Physics, ETH Zrich, Zrich 8093, Switzerland. 5 INRIA Rocquencourt, Domaine de Voluceau, B.P. 105, Le Chesnay Cedex 78153, France. 6 ICREAInstitucio Catalana de Recerca i Estudis Avanats, Barcelona E08010, Spain. Correspondence and requests for materials should be addressed to A.A. (email: mailto:[email protected]

Web End [email protected] ).

NATURE COMMUNICATIONS | 4:2263 | DOI: 10.1038/ncomms3263 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 1

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms3263

Understanding the structure of correlations within our current description of nature, based on quantum physics, is a fundamental open problem. In particular, one

would like to characterize the set of quantum correlations, that is, correlations which can result from local measurements on quantum states. Pioneering work by Popescu and Rohrlich1 showed that the no-signalling (NS) principlethat is, the impossibility of instantaneous communicationdoes not sufce to recover this quantum set. Indeed, they provided examples of correlations between two parties compatible with the NS principle but without any quantum realization. The most paradigmatic example of these supra-quantum correlations is the so-called Popescu-Rohrlich (PR) box, also studied by Tsirelson2. The search for better principles separating supra-quantum correlations from quantum ones, or ideally a complete characterization of the quantum set, was started.

An important boost to this search was because of Van Dam3, who introduced the idea that the existence of supra-quantum correlations, while not violating the NS principle, could have implausible consequences from an information-processing point of view. Van Dam3 showed that distant parties having access to PR-boxes can render communication complexity trivial and argued that this could be a reason for the non-existence of these correlations in nature. Since then, intensive effort has been devoted to the search for information principles characterizing the set of quantum correlations, for example, the aforementioned non-trivial communication complexity3,4, information causality5 and macroscopic locality6.

Recently, it has been shown that intrinsically multipartite principles are essential to characterize the set of quantum correlations. It was proven by Gallego et al.7 that there exist supra-quantum correlations for three parties that cannot be detected by any bipartite principle. Unfortunately, most of the existing principles for quantum correlations are formulated in a bipartite setting and their multipartite generalization is unclear, apart from the trivial one in which the parties are split in two groups and the principle is applied to each bipartition. In this sense, note that even the NS principle has a bipartite formulation in the multipartite scenario: correlations among n distant parties satisfy the NS principle whenever the marginal distribution seen by a subset of the n parties is independent of the choice of measurements by the remaining ones.

In this work, we introduce the concept of local orthogonality (LO), an intrinsically multipartite principle for correlations. The principle is based on a denition of orthogonality (or exclusiveness) between events involving measurement choices and results by n distant parties: we dene some events to be orthogonal, or exclusive, whenever they involve different outcomes of the same local measurement by at least one of the parties. Operationally, we demand that the sum of the probabilities of mutually exclusive events is less than or equal to one, which implies a restriction on possible correlations. We provide an information-processing interpretation of this new principle in terms of a distributed guessing problem (DGP). We then show how the principle implies a highly non-trivial structure in the space of correlations. First, we prove that, whereas the set of LO correlations coincides with the set of NS correlations for two parties, it is strictly smaller for more than two parties. Second, by exploiting the non-equivalence of LO and the NS principle in the multipartite case, it is demonstrated how LO can also be used to detect the nonquantumness of some supra-quantum, bipartite NS correlations. In particular, we prove that distributed copies of the PR-box violate LO, and show how one can get very close to the boundary of the quantum set of bipartite correlations (Tsirelsons bound) by imposing LO. Finally, we prove that the intrinsically multipartite formulation of the principle allows one to detect supra-quantum correlations for which any bipartite principle fails.

In deriving all these results, we exploited a connection between LO correlations and graph theory, related to the constructions derived by Cabello et al.8 in the study of quantum contextuality. In fact, there is a natural notion of orthogonality (also called exclusiveness) between events in contextuality scenarios, which are dened by sets of measurements sharing some measurement outcomes (two events are orthogonal if they correspond to different outcomes of a given measurement). For instance, several works have studied how the violation of the corresponding orthogonality conditions can lead to supra-quantum correlations9,10, or how these orthogonality conditions can be used to provide upper bounds to the quantum violation of non-contextuality inequalities8.

ResultsDenition. We start by presenting the formal denition of the LO principle in a general Bell scenario involving n distant parties, each of them having an access to a physical system. Each party can perform m different measurements on the system, getting one out of d possible outcomes. This scenario is denoted by (n, m, d). The measurement applied by party i is denoted by xi, and the corresponding outcome by ai, with iA{1, y, n}, xiA{0, y, m 1} and aiA{0, y, d 1}. The correlations among the parties

are described by the joint conditional probability distribution P(a1yan|x1yxn), representing the probability for the parties to get outcomes a1, y, an when making measurements x1, y, xn.

The main aim of LO is to introduce a notion of exclusiveness in the space of events. Consider rst two different events e and e0 given by e (a1yan|x1yxn) and e0 (a10 yan0 |x01yx0n). We

call these two events locally orthogonal or simply orthogonal, if they involve different outputs of the same measurement by (at least) one party; that is, if for some i we have aiaai0 whereas xi xi0. We then call a collection of events {ei} orthogonal, or

exclusive, if the events are pairwise orthogonal, and impose that for any set of orthogonal events, the sum of their probabilities must not be larger than one,

XiPei 1: 1

This requirement is the LO principle. To summarize: the LO principle (i) introduces a notion of orthogonality between two events, (ii) imposes that any number of events are orthogonal whenever they are pairwise orthogonal and (iii) requires that the inequality (1) is satised for any set of orthogonal events.

The notion of orthogonality is rather natural in the case of two events, and the requirement (1) is automatically satised for NS correlations. In fact, consider two LO events e1, e2 with aiaai0 and xi xi0 as before. These two events can be seen as different

outcomes of a correlated measurement in which: (i) party i rst measures xi and announces the outcome to the other parties and(ii) the other parties apply measurements depending on this outcome, in particular they measure x1, y, xn, if the outcome is ai, and x01, y, x0n otherwise. Thus, as e1 and e2 are outcomes of the same (correlated) measurement, the requirement (1) immediately follows from normalization. Note that the NS principle is essential for this correlated measurement to be meaningful, as it is possible to dene the marginal probability for party i in the rst step of the correlated measurement independently of the successive actions by the other parties.

The principle, however, becomes more restrictive when considering more events, in which the previous reasoning does not apply any longer. As mentioned above, we extend the initial denition of orthogonality for two events to more events by demanding pairwise orthogonality. It is precisely this extended and intrinsically multipartite formulation that makes the principle non-trivial, as it involves summing probabilities conditioned on

2 NATURE COMMUNICATIONS | 4:2263 | DOI: 10.1038/ncomms3263 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms3263 ARTICLE

different measurements. Taken together, all the restrictions on the conditional probability distributions implied by LO dene the set of LO inequalities (1) for the (n, m, d) scenario. The set of LO correlations is then the set of conditional distributions P(a1yan|-

x1yxn) satisfying all the LO inequalities.

Moreover, we can dene the sets of conditional probability distributions that obey LO for a certain number of copies in the following sense. A given distribution for the (n, m, d) scenario can be thought of as provided by some device shared between the n parties, each having access to one input and output of the device. If the distribution provided by the device is compatible with LO, a natural question is whether a larger distribution coming from several copies of such a device distributed among more parties necessarily satises LO. As we will explain below, the answer to this question is negative; that is, LO displays activation effects and, hence, we have a hierarchy of sets. The largest set in this hierarchy, denoted LO1, is the set of all distributions in the (n, m,

d) scenario that obey the LO inequalities for this scenario. Now consider k copies of a device characterized by a distribution P, distributed among kn parties, each of which has access to one input of only one device. If the distribution Pk of the kn-partite global device obeys all the LO inequalities for the scenario (kn, m, d), we say that P satises LOk, and belongs to LOk. We denote

by LO1 the set of distributions for (n, m, d) that obey the LO

inequalities for any number of copies.

Having stated the LO principle, our main goal is the study of the sets LOk of LO correlations. As we shall see, the LO principle

turns out to be very powerful for ruling out non-quantum correlations. As in the case of contextuality8, graph theory is perfectly suited for our purposes. We consider the (md)n possible events in the (n, m, d) scenario and map them on an orthogonality graph with (md)n vertices, where two vertices are connected by an edge if and only if the corresponding events are locally orthogonal. For instance, Fig. 1 shows the orthogonality graph of the (2, 2, 2) scenario. In the graph theory, a clique in a graph G (V, E) is a subset of vertices CDV such that the

subgraph induced by C is complete, that is, such that all pairs of vertices in C are connected by an edge in G. A clique is maximal if it cannot be extended to another clique by including a new vertex. Clearly, any clique in the orthogonality graph of events gives rise to an LO inequality (and vice versa), as all events in the clique are

connected and, thus, are pairwise orthogonal. Therefore, the problem nd all the optimal LO inequalities is equivalent to nd all maximal cliques of the associated orthogonality graph. While the problem of nding all maximal cliques of a graph is known to be NP-hard11, there exist software packages12,13 that provide the solution for small graphs. We have used these packages to derive and partly classify LO inequalities for various Bell scenarios, which will be presented elsewhere. Note, however, that in principle, while the problem of nding the maximal cliques is NP-hard for general graphs, this may no longer be the case for graphs associated to correlations among distant parties. Indeed, these graphs may represent a subset of all possible graphs that does not include the hard instances of the problem.

Distributed guessing problems. Before moving on to the characterization of LO correlations, we provide an interpretation of the principle from an information-processing viewpoint. To this end, we introduce the notion of a DGP.

Guessing problems are ubiquitous in science. In the standard formulation (see Fig. 2a), an observer has the access to some data x, which depends on some initial parameter a, that is x f(a).

From the observed data, the observer should make a guess, a, of the initial parameter. His goal is to maximize the probability of guessing correctly.

Guessing problems can be easily adapted to distributed scenarios. It is convenient to present the DGP as a game and to phrase it in terms of vectors of symbols. Consider then a nonlocal game in which a referee has access to a set of vectors of n symbols with values in {0, y, d 1}. Denote this set by S and its

size by |S|, which can be less than dn in general. Now, the referee chooses a vector (a1, y, an) uniformly at random from S, and encodes it into a new vector of, again, n symbols using a function f. However, the new symbols can now take m values and, thus, f:S - {0, y, m 1}n. The resulting vector is (x1, y, xn) f

(a1, y, an). These n symbols are distributed among n distant players who cannot communicate and must produce individual guesses a1,

y, an. Their goal is to guess the initial input to the function, that is, they win whenever aj aj for all j. Note that the encoding function f

and the set S are known in advance to all the players.For some f, for example, for xj aj, this task is very simple.

However, there exist functions for which the task becomes

(00|00) (01|00) (00|01) (01|01)

(11|01)

1 , n

(10|00)

(00|10)

(11|00)

(01|10) (00|11) (01|11)

(11|11)

(10|01)

x x1 xn

a a1 an

(11|10)

(10|010)

Figure 1 | Orthogonality graph of the (2,2,2) scenario. As mentioned in the text, each possible event corresponds to a node, whereas the edges connect locally orthogonal events.

Guess Guess Guess

Figure 2 | Distributed guessing problems. In the standard scenario (a), an observer has to guess the value of a parameter a given only some function of it, x f(a). In the distributed scenario (b), the input parameter is a vector

of n symbols, (a1, ,an), and so are the data given to the players (x1, y, xn). Each of player has an access to just one of the symbols xj and has to guess the corresponding initial parameter aj. The game is won when all the players guess correctly.

(10|11)

NATURE COMMUNICATIONS | 4:2263 | DOI: 10.1038/ncomms3263 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 3

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms3263

extremely difcult. For a xed size |S|, the most difcult functions are those for which the maximum guessing probability is equal to 1/|S|. The players can always achieve this guessing probability by agreeing beforehand on one of the |S| possible outputs, regardless of the xj. As the input is uniform on S, their guess is correct with probability 1/|S|. A DGP is thus maximally difcult whenever this strategy is optimal, that is, whenever it is impossible to provide a better estimate of the input than random guessing. For such an f, having access to the symbols xj does not provide any useful information to the parties. Note that non-trivial maximally difcult functions are possible only in distributed scenarios. In standard single-observer guessing problems, the only maximally difcult function is the one dened by a constant function f, which trivially erases any information about the input. An example of a difcult function in the (n, 2, 2) scenario for odd n and classically correlated players is f(a1, y, an) (an, a1, y, an

1) dened

on the set S of inputs satisfying a1"y"an 0. This is the

guess-your-neighbours-input task considered in the work by Almeida et al.14

As we prove in Methods, a DGP is maximally difcult for players sharing classical correlations (classical players) if, and only if, it corresponds to an LO inequality. Hence, in order to win the game with a probability larger than 1/|S|, they need to share correlations violating LO. In particular, quantum correlations provide no advantage over the trivial strategy of randomly guessing the solution.

The NS principle. The rst question we ask while characterizing LO correlations is how they relate to the set of NS correlations, denoted by N S. For bipartite scenarios, the two principles dene

the same set of correlations, as was already noticed in the work of Cabello et al.8 (in Methods, we give a slightly different proof that emphasizes the connection with LO). However, the equivalence between LO and NS breaks down while moving to the multi-partite scenario. We exploited the graph-theoretical approach mentioned in the previous section to generate the list of LO inequalities for different scenarios, and then classied them into equivalence classes under relabellings, permutations of parties and NS constraints (using a Mathematica as well as MATLAB code kindly provided to us by J.D. Bancal). Already in the simplest tripartite scenario (3, 2, 2), we nd one and only one class of non-trivial LO inequalities, in which non-trivial means that the inequalities are violated by some NS correlations. This inequality turns out to be the GYNI inequality14, which in the tripartite case reads P(000|000) P(110|011) P(011|101) P(101|110)r1. It

is easy to see by simple inspection that GYNI is an LO inequality. As shown in the studies of Almeida et al.14, the maximum of the GYNI inequality over N S is equal to 4/3. Our numerical data

suggest that the gap between LO1 and N S increases with the

number of parties: in the (4, 2, 2) scenario, we nd 35 equivalence classes. Unfortunately, for more parties (n44), even the simplest scenario (n, 2, 2) becomes computationally intractable because of the large size of the orthogonality graph. Nevertheless, examples of such inequalities for larger n as well as m and d are known and can be constructed from unextendible product bases15 by using the method discussed in Augusiak et al.16,17 (see also the work of Acin et al.18).

It is worth mentioning that all the known examples of nontrivial, tight (in the sense of dening a tight Bell inequality19) information tasks with no quantum advantage, given in Almeida et al.14, Augusiak et al.16,17, Acn et al.18, are examples of LO inequalities. It is an interesting working conjecture to prove that any non-trivial and tight information task with no quantum advantage denes an LO inequality. In particular, this would

imply that any non-trivial tight Bell inequality in a bipartite scenario has quantum violations.

Supra-quantum correlations. The LO principle is naturally satised by quantum correlations. Indeed, orthogonal events can be associated with measurements described by projectors with disjoint supports (see Methods for details). We now investigate the use of the LO principle as a tool to detect post-quantum NS correlations. Clearly, those correlations violating GYNI are in contradiction with LO as well. However, the situation turns out to be much richer, already for two parties. In principle, one might think that LO would be useless for the detection of supra-quantum bipartite correlations because of the equivalence with NS. However, this intuition is not correct. We can show that postulating LO also on the many-party level leads to the detection of non-quantumness of bipartite correlations. Given some bipartite correlations, the main idea consists of distributing k copies of these among 2k parties, such that one party has access to one part (input and output) of only one bipartite box. In the resulting 2kpartite scenario, the LO principle is stronger than the NS principle. Thus, it may happen that the initial bipartite correlations violate LO when distributed among different parties in a network. The idea is similar in spirit to the network approach to nonlocality presented by Cavalcanti et al.20

A PR-box is a hypothetical device taking binary inputs and giving binary outputs, which obey PR(ab|xy) 1/2 if a"b xy

and PR(ab|xy) 0 otherwise1. These boxes are known to be more

non-local than what quantum theory allows. For instance, they provide a violation of the ClauserHorneShimonyHolt Bell inequality21 larger than Tsirelsons bound for quantum correlations22. PR-boxes are bipartite NS devices, and therefore might naively be expected to satisfy LO. However, we prove now that when distributed in networks they violate LO.

Consider k copies of a PR-box, distributed among 2k parties as shown in Fig. 3. The conditional probability distribution is:

Pa1b1 . . . akbk j x1y1 . . . xkyk Y

PRajbj j xjyj; 2

where j labels the k boxes. Already for k 2, we nd LO

inequalities violated by these two copies of the PR-box, and hence PR-boxes do not satisfy LO2. One example of such an inequality is P(0000|0000) P(1110|0011) P(0011|0110) P(1101|1011)

P(0111|1101) r1. For a PR-box, the left-hand side is equal to 5/4. We can also analyse noisy versions of the PR-box given by Pq qPR (1 q)PI, where PI(ab|xy 1/4) for all a, b, x, y. We

nd that two copies of a noisy PR-box violate LO down to qE0.72, which is close to Tsirelsons bound q 1= 2

p 0:707

(meaning that noisy boxes with q 1= 2

p can be simulated with

x1 y1

k parties

xk yk

Figure 3 | Network of PR-boxes. We consider k copies of a PR-box shared among 2k parties. Each party has an access to one part of a box.

4 NATURE COMMUNICATIONS | 4:2263 | DOI: 10.1038/ncomms3263 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms3263 ARTICLE

quantum states and measurements). Detailed derivations of these

results are presented in Methods.

An immediate consequence of these results is that LO also rules out all extremal boxes in the (2, 2, d) and (2, m, 2) scenarios. The rst case follows from the fact that any extremal box in the (2, 2, d) case can always be used to simulate a PR-box arbitrarily well23. For the (2, m, 2) scenario, all the extremal boxes were characterized by Jones et al.24 (see also the work by Barrett et al.25). There, it is shown that, up to symmetries, an extremal non-local box is equivalent to a PR-box if one restricts the considerations to the rst two inputs out of the m possible choices. Hence, any LO inequality violated by a PR-box is also violated by any extremal non-local bipartite binary box.

It is also interesting to compare LO with information causality (IC)5, another proposal for a physical principle to single out quantum correlations. A natural question then is whether and when LO can do better than IC in ruling out supra-quantum correlations. Following Allcock et al.26, we study LO predictions for different families of NS correlations. In some situations, LO provides a bound to the set of quantum correlations which is tighter than the known bounds obtained from applications of IC, as can be seen in Fig. 4. Hence, LO rules out correlations that were not excluded before by IC.

So far, we have focused on how some bipartite supra-quantum correlations can be excluded by LO. Owing to the intrinsically multipartite formulation of the principle, we expect it to be of particular relevance for the study of genuine multipartite correlations among more than two parties. As an example, we study how well LO performs for extremal NS non-local correlations in the (3, 2, 2) scenario. All these extremal NS boxes were computed by Pironio et al.27 and any NS correlations in this scenario can be obtained by mixing them. These extremal boxes can be grouped into 46 equivalence classes under symmetries, the rst class corresponding to deterministic local points, whereas the other 45 are non-local. The latter can be interpreted as the maximally non-local correlations in the (3, 2, 2) scenario

compatible with the NS principle. LO can be shown to rule out all these maximally non-local boxes. We follow a method similar to the one for PR-boxes presented in Methods, although for some cases the tripartite boxes required a slightly more general approach in terms of weighted graphs. The details of these derivations are beyond the scope of the present manuscript and will be presented elsewhere. We nd that every maximally nonlocal box in (3, 2, 2) violates either LO1 or LO2, and hence cannot have a quantum realization.

We conclude this part with a couple of observations. First, LO is, to our knowledge, the rst principle able to rule out all the known examples of extremal non-local boxes. We have shown it rst for the only maximally non-local box in the (2, 2, 2) scenario (the PR-box), then for maximally non-local boxes in the (2, m, 2) and (2, 2, d) scenarios, as well as for all extremal boxes in the (3, 2, 2) case. Second, the intrinsically multipartite formulation of LO allows detecting correlations, for which any bipartite principle fails. For instance, the correlations provided by Gallego et al.7 violate GYNI and, consequently, also LO, but satisfy every bipartite principle. Moreover, box number 4 described in Pironio et al.27 is an example of a tripartite NS box, which cannot be ruled out by any bipartite principle28, but which violates LO.

DiscussionMultipartite principles are necessary to understand the structure of quantum correlations from an information perspective. Local orthogonality is a principle for correlations that has an intrinsically multipartite formulation. It has a natural interpretation in terms of DGPs. Moreover, it can be used in the study of correlations by applying standard techniques from graph theory. We have shown here that the principle gets very close to the set of quantum correlations and detects all known maximally non-local boxes as supra-quantum, including those for which any bipartite principle fails.

We believe that LO will be an essential ingredient for the characterization and understanding of correlations. An intriguing question is to understand the exact relation between this set and the set of quantum correlations. Miguel Navascus rst noticed that the set of quantum correlations is strictly smaller than LO1,

as also proved by Fritz et al.29 Are there simple additional principles that, together with LO, completely characterize the set of quantum correlations?

Another interesting line of research consists in extending our approach, here formulated for Bell scenarios, to other frameworks. In fact, the principle is rather general: after introducing a notion of orthogonality in a space of events, the whole machinery of graph theory and copies of the graph (networks) automatically applies. A natural framework for its application is the study of contextuality scenarios where, as mentioned, there is a natural notion of orthogonality (or exclusiveness). In fact, our approach has successfully been applied to the study of quantum contextuality in several recent works2931.

Methods

Maximally difcult DGPs and LO inequalities. Our goal here is to prove that imposing that correlations do not provide any advantage for DGP involving maximally difcult functions f is equivalent to LO. For such an f and any correlations P(a1yan|x1yxn), providing no advantage for the DGP dened byf means that

j j X

a ; ... ;a 2S

P a1 . . . an j f1a1; . . . ; an . . . fna1; . . . ; an

1.0

0.70

[afii9841][notdef]0.65

0.8

0.60

0.00 0.10 0.2

0.6

[afii9828]

[afii9841]

0.4

0.2

0.0

0.0 0.2 0.4

[afii9828]

0.6 0.8 1.0

Figure 4 | IC versus LO performance. Comparison of both principles for detecting supra-quantum correlations in the (2,2,2) scenario. We consider the family of correlations parametrized as Pab j xy xPRab j xy

gPLab j xy 1 x gPI, where PL(ab|xy) da,0db,0. The curves show the

bounds provided by the 1 AB level of the NPA hierarchy32,33 (black), LO2

(blue dashed), IC (red dotted) and the edge of the crossed-out region corresponds to NS correlations and bounds that allowed parameter space. Note that when g-0 (see inset), IC approximates the quantum set better than LO2, which is consistent with the fact that IC recovers Tsirelsons bound for g 0, whereas LO reaches E0.72 for two copies of the device.

However, LO beats the known IC bound for other parameter values, ruling out correlations that were not excluded before.

1 S

j j

; 3

where f1, y, fn refer to the components of the vector f, and xj fj(a1, y, an) is the

input that party j receives. Note that, for simplicity, and as the goal of the parties is to provide a correct guess of the initial parameters, we slightly abuse notation and replace all aj by aj. In order to prove the correspondence, we now show that

NATURE COMMUNICATIONS | 4:2263 | DOI: 10.1038/ncomms3263 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 5

ARTICLE NATURE COMMUNICATIONS | DOI: 10.1038/ncomms3263

functions f that are maximally difcult for classical players are precisely those which have the property that if f(a1, y, an) and f(a01, y, a0n) are both dened, then there exists some j for which ajaa0j, but fj(a1, y, an) fj(a01, y, a0n). Given

that f varies over all those partial functions having this property, the DGP inequalities (3) dene all LO inequalities in the (n, m, d) scenario.

We rst prove the only if direction by contradiction. Assume there exist a1, y,

an and a01, y, a0n, in both of which f is dened such that for every party j either aj a0j or fj(a1, y, an)afj(a01, y, a0n) holds true. Then the following classical

strategy performs better than random guessing: for those j with aj a0j, let them

output this particular value independently of their input; for those with ajaa0j and

fj(a1, y, an)afj(a01, y, a0n), choose some function gj such that aj gj(fj(a1, y,

an)) and a0j gj(fj(a01, y, a0n)), and let them output gj(xj). This strategy recovers all

correct values both for the a1, y, an as well as for the a01, y, a0n, and therefore performs better than random guessing.

Conversely, we need to show that if f has this property, then using local operations only cannot be more successful than random guessing. Thanks to convexity, it is enough to consider deterministic local strategies. If a deterministic strategy is better than random guessing, there needs to exist at least a1, y, an and

a01, y, a0n such that the strategy works on both of these. In particular, this means that, for each party j, either aj a0j, or party j needs to be able to tell the two cases

apart via xj, so that fj(a1, y, an)afj(a01, y, an). This implies that f cannot have the property described above.

NS and LO1 in bipartite scenarios. We prove that in the bipartite case, LO1 and NS dene the same set of correlations. Although this is already known8, here we give a slightly different proof that emphasizes the connection with LO. To simplify the notation, in the bipartite scenario, measurements and results by the two parties are labelled by x, y and a, b, so that correlations read P(ab|xy).

Let us start by characterizing the possible sets of locally orthogonal events. Recall that two events are locally orthogonal if for at least one party the settings are identical but the outcomes are different. Consider a set of locally orthogonal events that contains (ab|xy) and (a0b0|x0y) with x0ax. Then, this set cannot contain any event of the form (a00b00|x00y0) with y0ay, as it could not be locally orthogonal to both other events. From this intuition, we nd that the sets of pairwise orthogonal events are either {(ab|xoA(a)): a, b 0, y, d 1} for xed x, or {(ab|oB(b)y): a,

b 0, y, d 1} for xed y with oW: {0, y, d 1}-{0, y, m 1} (W A, B)

being some map.

We start by showing that sets of the rst kind have the desired property;the proof for sets of the second kind is analogous. Take two such events (ab|xoA(a))a(a0b0|xoA(a0)). Then, either aaa0 and orthogonality holds on Alices side, or bab0 and orthogonality follows from Bob. This proves that we have a set of LO events. To see that the set is maximal, consider an arbitrary event

~b j ~x. If

~x x and oA, then this event is already in the set. Otherwise, LO fails

between

~b j ~x and

~b j xoA. Hence, it is impossible to add any event to

the set, that is, the set is maximal.

Now we prove that every maximal LO1 set is of one of these two forms. It is enough to show that every LO1 set is contained in a set of this form. As noted above, for events in an LO set, one of the parties is restricted to using a single input. Hence, without the loss of generality, we can take x to be xed. As every two orthogonal events differ on at least one outcome, there exists a function o(a, b), such that every element in the set is of the form (ab|xo(a, b)). We complete the proof by showing that o(a, b) does not depend on b. The existence of a and b, b0 with o(a, b)ao(a, b0) would imply that (ab|xo(a, b)) and (ab0|xo(a, b0)) are not orthogonal, contradicting the assumption.

We denote by N S the set of distributions P(ab|xy) satisfying NS. The

conditions for NS are

Xd 1b0Pab j xy Xd 1b0Pab j xy0; Xd 1a0Pab j xy Xd 1a0Pab j x0y 4

and we also have the normalization conditions

h jY

x . . . Y

x . . .

x . . . Y

j i; 5

where the maximization runs over all possible states |CS and projectors fQx

acting on an arbitrary Hilbert space. Note that the maximization can be carried out over projective measurements without the loss of generality, as the ancilla needed for a general measurement can be absorbed in the denition of the state |CS. The term in the parenthesis is equal to the sum of two orthogonal projectors, as

Qx a

Qxa 0. Thus, this sum is upper bounded by the identity operator and the LO inequality follows.

Two PR-boxes violate LO. We classify events as either possible or not possible for this many-copy box as follows. An event (ab|xy) for one PR-box is possible if a"b xy. Hence, PR-box correlations may be written as

PRab j xy

if the event is possible;otherwise: 6 In the case of k boxes, an event (a1b1?akbk|x1y1?xkyk) is possible if

aj"bj xjyj for all jA{1, y, k}. Then, the general form for the k-box probability

(2) is

Pa1b1 . . . akbk j x1y1 . . . xkyk

2 k

if the event is possible; otherwise: 7 Consider a clique CDV in the orthogonality graph G (V, E) of the scenario

(2k, 2, 2) and the corresponding LO inequality LO(C). Dene the set CpDC to be

the subset of possible events in C. Then, the multipartite box (7) violates LO(C) if, and only if, it violates LO(Cp). In particular, in order to exclude the PR-box, it is sufcient to nd a clique of size larger than 2k in the orthogonality graphGposs (Vp, Ep) of possible events for box (7). This problem becomes signicantly

easier, as |Vp| 8k, compared with |V| 16k, for the initial graph (compare Figs 1

and 5). Already for k 2, there exist cliques of size larger that 4. We found that all

of them have size 5, and one example is given by: {(0000|0000), (1110|0011), (0011|0110), (1101|1011), (0111|1101)}.

Consider now two copies of a noisy PR-box given by Pq qPR (1 q)PI,

where PI(a,b|x,y) 1/4 for all a, b, x, y. Now all events become possible and one

should consider the full list of LO inequalities for (4, 2, 2). However, one can still consider this ve-term inequality as associated to a non-maximal clique in the orthogonality graph of the (4, 2, 2) scenario, and complete it to a maximal clique. This gives an inequality with additional terms corresponding to events that are

(00|00)

(00|10)

(00|01)

(10|11)

Pd 1a;b0 Pab j xy 1, 8x, y. We now prove that LO1 N S in the present bipartite setting.

LO1 N S: all optimal LO1 inequalities are of the form Pd

1 a;b0

Pab j xoAa 1, modulo exchanging the parties. We x any a0, y and y0 and

consider the function oA(a) y, if a a0 and oA(a) y0 if aaa0. The LO

inequality yields

Pd 1a 6 a ;b0 Pab j xy0 Pd

1b0 Pa0b j xy 1. Together with

(01|11)

the normalization equation

Pd 1a;b0 Pab j xy0 1, this implies Pd

1 b0

Pa0b j xy Pd

1b0 Pa0b j xy0. As the same inequality can be derived with y and

y0 interchanged, we nd that it actually needs to be an equality, which is (4).

N S LO1: start from the normalization condition Pd

1a;b0 Pab j xy 1.

Using the NS equation (4), we can transform it into an equality of the form

Pd 1a;b0 Pab j xoAy 1 for any given x and oA. It follows that N S LO1, and thus LO1 N S, in the bipartite scenario.

Quantum correlations satisfy LO. It is straightforward to see that LO inequalities are satised by the set of quantum correlations, denoted Q, that is, Q LO1. For

simplicity, we give the proof for an inequality involving two LO events. The generalization to an arbitrary LO inequality, and in particular to any number of copies is straightforward and follows from the property that in quantum

mechanics, a set of projective measurements that can be pairwise implemented, can be jointly implemented (that is, pairwise orthogonality between projectors implies orthogonality of all the projectors).

Consider two LO events e1 (a1yan|x1yxn) and e2 (a01ya0n|x01yx0n)

with aiaa0i, xi x0i, and the corresponding inequality p(e1) p(e2)r1. The

maximization of the sum of these two probabilities over quantum correlations reads

max

j i;Q

n o

(11|01)

(11|10)

(11|00)

Figure 5 | Orthogonality graph of possible events for a single PR-box.

It coincides with Figure 2 in the work of Sadiq et al.34, in which the authors studied the CHSH inequality.

6 NATURE COMMUNICATIONS | 4:2263 | DOI: 10.1038/ncomms3263 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications

NATURE COMMUNICATIONS | DOI: 10.1038/ncomms3263 ARTICLE

impossible for the PR-box, but which are possible for a noisy PR-box. In this way, we have found that the distribution

Pa1b1a2b2 j x1y1x2y2 qPRa1b1 j x1y1 1 q14

qPRa2b2 j x2y2 1 q14

violates LO for q\0.72. An example of such an LO inequality is given by the following set of 10 LO events: {(1111|0000), (1100|1010), (0100|1100),(0011|0001), (0010|0111), (1011|0000), (0101|1100), (1101|1100),(1010|0110), (1001|0100)}.

It appears plausible to conjecture that the generalization of the previous approach to an arbitrary number of parties converges to Tsirelsons bound q 1= 2

p 0:707 in the limit of an innite number of parties, although we did

not yet nd any proof.

References

1. Popescu, S. & Rohrlich, D. Nonlocality as an axiom. Found. Phys. 24, 379385 (1994).

2. Tsirelson, B. Some results and problems on quantum Bell-type inequalities. Hadronic J. Suppl. 8, 329345 (1993).

3. van Dam, W. Nonlocality and Communication Complexity. PhD thesis (University of Oxford, 2000).

4. Brassard, G. et al. Limit on nonlocality in any world in which communication complexity is not trivial. Phys. Rev. Lett. 96, 250401 (2006).

5. Paw"owski, M. et al. Information causality as a physical principle. Nature 461, 11011104 (2009).

6. Navascus, M. & Wunderlich, H. A glance beyond the quantum model. Proc. R. Soc. A 466, 881890 (2010).

7. Gallego, R., Wringer, L. E., Acn, A. & Navascus, M. Quantum correlations require multipartite information principles. Phys. Rev. Lett. 107, 210403 (2011).

8. Cabello, A., Severini, S. & Winter, A. (Non-)Contextuality of physical theories as an axiom. Preprint at http://arXiv.org/abs/1010.2163

Web End =http://arXiv.org/abs/1010.2163 (2010).

9. Specker, E. Die logik nicht gleichzeitig entscheidbarer aussagen. Dialectica 14, 239246 (1960).

10. Liang, Y. C., Spekkens, R. W. & Wiseman, H. M. Speckers parable of the over-protective seer: a road to contextuality, nonlocality and complementarity. Phys. Rep. 506, 139 (2011).

11. Karp, R. M. in Complexity of Computer Computation. (eds Miller, R. E. & Thatcher, J. W.) 85103 (Plenum, 1972).

12. Takeaki, U. Mace: maximal clique enumerator (2005); Version 2.0.13. Niskanen, S. &stergrd, P. Cliquer (2010); Version 1.21..14. Almeida, M. L. et al. Guess your neighbors input: a multipartite nonlocal game with no quantum advantage. Phys. Rev. Lett. 104, 230404 (2010).

15. Bennett, C. et al. Unextendible product bases and bound entanglement. Phys. Rev. Lett. 82, 53855388 (1999).

16. Augusiak, R. et al. Bell inequalities with no quantum violation and unextendable product bases. Phys. Rev. Lett. 107, 070401 (2011).

17. Augusiak, R. et al. Tight Bell inequalities with no quantum violation from qubit unextendible product bases. Phys. Rev. A 85, 042113 (2012).

18. Acn, A., Almeida, M. L., Augusiak, R. & Brunner, N. Guess your neighbours input: no quantum advantage but an advantage for quantum theory. Preprint at http://arXiv.org/abs/1205.3076

Web End =http://arXiv.org/abs/1205.3076 (2012).

19. Masanes, L. Tight Bell inequality for d-outcome measurements correlations. Quantum Information and Computation 3, 345358 (2003).

20. Cavalcanti, D., Almeida, M. L., Scarani, V. & Acn, A. Quantum networks reveal quantum nonlocality. Nat. Commun. 2, 184 (2011).

21. Clauser, J. F., Horne, M. A., Shimony, A. & Holt, R. A. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880884 (1969).

22. Cirelson, B. S. Quantum generalizations of Bells inequality. Lett. Math. Phys. 4, 93100 (1980).

23. Barrett, J. et al. Nonlocal correlations as an information-theoretic resource. Phys. Rev. A 71, 022101 (2005).

24. Jones, N. & Masanes, L. Interconversion of nonlocal correlations. Phys. Rev. A 72, 052312 (2005).

25. Barrett, J. & Pironio, S. Popescu-Rohrlich correlations as a unit of nonlocality. Phys. Rev. Lett. 95, 140401 (2005).

26. Allcock, J., Brunner, N., Paw"owski, M. & Scarani, V. Recovering part of the boundary between quantum and nonquantum correlations from information causality. Phys. Rev. A 80, 040103 (2009).

27. Pironio, S., Bancal, J.-D. & Scarani, V. Extremal correlations of the tripartite no-signalling polytope. J. Phys. A. Math. Theor. 44, 065303 (2011).

28. Yang, T. H., Cavalcanti, D., Almeida, M. L., Teo, C. & Scarani, V. Information-causality and extremal tripartite correlations. New J. Phys. 14, 013061 (2012).

29. Fritz, T., Leverrier, A. & Sainz, A. A combinatorial approach to nonlocality and contextuality. Preprint at http://arXiv.org/abs/1212.4084

Web End =http://arXiv.org/abs/1212.4084 (2012).

30. Cabello, A. Simple explanation of the quantum violation of a fundamental inequality. Phys. Rev. Lett. 110, 060402 (2013).

31. Yan, B. Quantum correlations are tight bounded by exclusivity principle. Phys. Rev. Lett. 110, 260406 (2013).

32. Navascus, M., Pironio, S. & Acn, A. Bounding the set of quantum correlations. Phys. Rev. Lett. 98, 010401 (2007).

33. Navascus, M., Pironio, S. & Acn, A. A convergent hierarchy of semidenite programs characterizing the set of quantum correlations. New J. Phys. 10, 073013 (2008).

34. Sadiq, M., Badziag, P., Bourennane, M. & Cabello, A. Bell inequalities for the simplest exclusivity graph. Phys. Rev. A 87, 012128 (2013).

Acknowledgements

We greatly acknowledge the discussions with A. Cabello, M. Navascus and M. Pawloski. Research at the Perimeter Institute is supported by the Government of Canada through Industry Canada and by the Province of Ontario through the Ministry of Economic Development and Innovation. A.L. was supported by the SNF through the National Centre of Competence in Research Quantum Science and Technology. R.A. acknowledges the support from EU Project AQUTE and Spanish MINCIN through the Juan de la Cierva program. R.C. was supported by the German Science Foundation (grant CH 843/21) and the Excellence Initiative of the German Federal and State Governments (grant ZUK 43). A.B.S., J.B.B. and A.A. were supported by the European PERCENT ERC Starting Grant, Q-Essence, QCS and DIQIP Project, by the Spanish project FIS2010-14830, an FPU AP2009-1174 PhD grant and CatalunyaCaixa.

Author contributions

All authors contributed extensively to the work presented in this paper.

Additional information

Competing nancial interests: The authors declare no competing nancial interests.

Reprints and permission information is available online at http://npg.nature.com/reprintsandpermissions/

Web End =http://npg.nature.com/ http://npg.nature.com/reprintsandpermissions/

Web End =reprintsandpermissions/

How to cite this article: Fritz, T. et al. Local orthogonality as a multipartite principle for quantum correlations. Nat. Commun. 4:2263 doi: 10.1038/ncomms3263 (2013).

NATURE COMMUNICATIONS | 4:2263 | DOI: 10.1038/ncomms3263 | http://www.nature.com/naturecommunications

Web End =www.nature.com/naturecommunications 7

Word count: 7553

Show less

Abstract

Translate

Details

Title

Local orthogonality as a multipartite principle for quantum correlations

Author

Fritz, T; Sainz, Ab; Augusiak, R; Brask, J Bohr; Chaves, R; Leverrier, A; Acín, A

Pages

2263

Publication year

2013

Publication date

Aug 2013

Publisher

Nature Publishing Group

e-ISSN

20411723

Source type

Scholarly Journal

Language of publication

English

DOI

https://doi.org/10.1038/ncomms3263

ProQuest document ID

1424359125

Local orthogonality as a multipartite principle for quantum correlations

Jump to:

Full text

Abstract

Details

Suggested sources