The quantum maxima for the basic graphs of exclusivity are not reachable in Bell scenarios

The quantum maxima for the basic graphs of exclusivity are not reachable in Bell scenarios Lucas E. A. Porto,1Rafael Rabelo,1Marcelo Terra Cunha,2and Ad´ an Cabello3, 4 1Instituto de F´ ısica Gleb Wataghin, Universidade Estadual de Campinas (Unicamp), Rua S´ ergio Buarque de Holanda 777, Campinas, S˜ ao Paulo 13083-859, Brazil 2Instituto de Matem´ atica, Estat´ ıstica e Computac¸ ˜ ao Cient´ ıfica, Universidade Estadual de Campinas (Unicamp), Rua S´ ergio Buarque de Holanda 651, Campinas, S˜ ao Paulo 13083-859, Brazil 3Departamento de F´ ısica Aplicada II, Universidad de Sevilla, E-41012 Sevilla, Spain 4Instituto Carlos I de F´ ısica Te´ orica y Computacional, Universidad de Sevilla, E-41012 Sevilla, Spain A necessary condition for the probabilities of a set of events to exhibit Bell nonlocality or Kochen-Specker contextuality is that the graph of exclusivity of the events contains induced odd cycles with five or more vertices, called odd holes, or their complements, called odd antiholes. From this perspective, events whose graph of exclusivity are odd holes or antiholes are the building blocks of contextuality. For any odd hole or antihole, any assignment of probabilities allowed by quantum theory can be achieved in specific contextuality scenarios. However, here we prove that, for any odd hole, the probabilities that attain the quantum maxima cannot be achieved in Bell scenarios. We also prove it for the simplest odd antiholes. This leads us to the conjecture that the quantum maxima for any of the building blocks cannot be achieved in Bell scenarios. This result sheds light on why the problem of whether a probability assignment is quantum is decidable, while whether a probability assignment within a given Bell scenario is quantum is, in general, undecidable. This also helps to understand why identifying principles for quantum correlations is simpler when we start by identifying principles for quantum sets of probabilities defined with no reference to specific scenarios. I. MOTIVATION Bell nonlocality [1], i.e., the existence of correlations between outcomes of space-like separated measurements which are impossible to achieve with local hidden variable models (because there is no joint probability distribution that reproduces the probability distributions of all contexts), is one of the most fascinating properties of nature. However, among the many possible ways of being Bell nonlocal, only some of them occur in nature: those allowed by quantum theory. A fundamental question is: is there any principle that selects these ways? [2]. This question is related to a more profound question: how come the quantum? [3]. So far, all proposed principles for quantum nonlocal correlations, including no-signalling [2], information causality [4], macroscopic locality [5], and local orthogonality [6], have failed to identify the set of quantum correlations, even for the simplest Bell scenario [7]. However, one principle, called the totalitarian principle [8] or the principle of plenitude [9], is able to select the quantum correlations for all the scenarios where Bell nonlocality or Kochen-Specker (KS) contextuality can happen, under the assumption that the observables are ideal [10]. Ideal observables are those that, they and all their coarse–grained versions, can be measured ideally (i.e., giving the same outcome when the measurement is repeated, and without disturbing any compatible observable). Hereafter, we will refer to the contextuality produced by ideal observables as KS contextuality [9]. Every quantum Bell nonlocal correlation can be achieved with ideal observables [10]. Then, how is that we have a principle for the sets of quantum correlations for ideal observables but not for the sets of quantum nonlocal correlations? Arguably, the reason is that it is difficult to understand nonlocal correlations by only looking at Bell scenarios, because, as we shall show, they add constraints that make the mathematical characterisation of the sets of quantum correlations much more difficult than it is in other scenarios. The aim of this paper is to prove some results that illustrate this point. Specifically, we show that the most basic ingredients for KS contextuality cannot reach their maxima in any Bell scenario. The structure of the paper is the following. In Sec. II we collect some concepts and results that will be used later. In Sec. III we state our results. In Sec. IV, we discuss how they shed light on why it is so difficult to understand quantum Bell nonlocal correlations by only discussing Bell scenarios. We also list some open problems. The proofs are presented in Sec. V. II. CONCEPTS AND PREVIOUS RESULTS Here we recall some concepts and results of the graphtheoretic approach to correlations [11–14] that are required for the main result. Readers familiar with this approach can skip this section. In a nutshell, this approach associates a graph to the Bell nonlocality or KS contextuality witness of every Bell or noncontextuality inequality. By studying the properties of this graph, one can obtain, e.g., the classical, quantum, and more general bounds to the witness. To set the ground, we consider an experimental scenario, which is defined by a set of observables, their relations of compatibility (joint measurability), and a set of possible outcomes for each observable. We call an event a statement of the form ‘the outcomes a, . . . , c are obtained, when the observables x, . . . , z are, respectively, jointly measured.’ We will denote this event as a, . . . , c|x, . . . , z. Two events are said to be mutually exclusive if both include the same measurement but with different outcomes. Definition 1 Given a set of events {ei}n i=1, their graph of exclusivity is the n-vertex graph Gin which each event correarXiv:2305.19247v2 [quant-ph] 14 Feb 2024 2 sponds to a vertex and mutually exclusive events are represented by adjacent vertices. Definition 2 Avertex-weighted graph (G, w)is a graph G with vertex set V(G)endowed with a weight assignment w: V(G)→R+. Every Bell and noncontextuality inequality can be expressed as an upper bound Ωof a positive linear combination Sof probabilities of events, S=PiwiP(ei)≤Ω, with wi>0.Sis called a witness (of Bell nonlocality or KS contextuality, respectively). The connection to properties of a graph comes through the vertex-weighted graph of exclusivity (G, w)of the events eiin Swith weights wi. Allowing nonunit weights is important for this formalism to be applicable to general witnesses. However, hereafter, we will focus on witnesses in which wi= 1 for all iand thus on standard (unweighted) graphs. This case includes many important Bell and KS contextuality witnesses such as the ones in the Clauser- Horne-Shimony-Holt Bell inequality and the Klyachko-Can- Binicio˘ glu-Shumovsky noncontextuality inequality [15]. The maximum value of Sfor probability assignments consistent with the graph of exclusivity Gdepends on which type of assignments we consider. In a deterministic assignment, each eieither occurs with certainty or does not occur, i.e., P(ei)=1or P(ei)=0. We call a probability assignment classical if it can be written as a convex combination of deterministic assignments. The maximum of Sfor classical assignments is the independence number of G. Definition 3 The independence number of G, denoted by α(G), is the cardinality of the largest independent set of G. A set of vertices of Gis independent if all the vertices in it are pairwise nonadjacent. Quantum assignments are related to the concept of an orthogonal projective representation of G, while the maximum of Sis related to the Lov´ asz number of G. Definition 4 An orthogonal projective representation (OPR) of a graph Gis an assignment of a projector Πi(not necessarily of rank-one) onto a subspace of a d-dimensional Hilbert space Hto each i∈V(G), such that ΠiΠj= 0 = ΠjΠi(i.e., the subspaces onto which Πiand Πjproject are orthogonal), for all pairs i, j of vertices that are adjacent in G. Definition 5 The Lov´ asz number of Gis ϑ(G) := sup X i∈V(G) ⟨ψ|Πi|ψ⟩,(1) where the supremum is taken over all OPRs {Πi}of Gand unit vectors |ψ⟩(each of them is called a handle of the corresponding OPR) in any (finite or infinite) dimension. An OPR of Gis Lov´ asz-optimal if it achieves ϑ(G)with some handle. With these definitions, the above discussion can be formalised as the following theorem, proven in Ref. [12]. Theorem 1 Given a sum of probabilities of events Scorresponding to a Bell or a noncontextuality inequality, the maximum value of Sachievable in classical theories (local/noncontextual models) and the maximum value of S achievable in quantum theory satisfy SL / NC ≤α(G)Q ≤ϑ(G),(2) where Gis the graph of exclusivity associated to S,α(G) is the independence number of G, and ϑ(G)is the Lov´ asz number of G. In some scenarios, ϑ(G)might be only an upper bound to the maximum quantum value of S. For the purposes of this paper, a particular detail of the previous theorem deserves additional attention. This is the fact that, for some scenarios, the Lov´ asz number of the graph of exclusivity associated to a certain inequality might not be the exact maximum value of the inequality achievable in quantum theory, but only an upper bound of it. This may occur because, in a particular scenario, there might be restrictions which are not captured by the graph of exclusivity. For example, in the case of Bell scenarios, measurements are local measurements on spatially separated subsystems. This implies the restriction that the projectors of the OPR must be tensor products such that each of the factors is a projector associated with a certain subsystem. Moreover, given this tensor product structure, if two events are mutually exclusive because a local measurement on subsystem Ahas different results in each event, then another restriction is that the tensor products’ factors associated to Amust be orthogonal. In fact, in a Bell scenario there are different types of relations of exclusivity. For example, in a bipartite Bell scenario, two events can be mutually exclusive because a measurement on Ahas different results in each event, because of measurement on a different subsystem Bhas different results, or because both things occur simultaneously. To account for this, in this paper we will make use of the edge-coloured multigraph approach proposed in Ref. [13]. Definition 6 Amultigraph Γ=(V, E)is a graph with vertex set Vand edge set Esuch that multiple edges between two vertices are allowed. In particular, we will be interested in a special type of multigraphs that represent the relations of exclusivity between events in N-partite Bell scenarios: N-colour edge-coloured multigraphs G= (V, E)composed of Nsimple graphs GA= (V, EA), . . . , GN= (V, EN)that have a common vertex set Vand mutually disjoint edge sets EA, . . . ,EN, such that E=EA⊔. . . ⊔EN(where ⊔stands for disjoint union) and each Ejis of a different colour. That is, we will focus on multigraphs Gthat can be factorised into Nsimple subgraphs GA, . . . , GN, called factors, each of which spans the entire set of vertices of G, and such that all together collectively exhaust the set of edges of G. The factor GJrepresents the exclusivity relations associated to party (subsystem) J. Throughout the paper, we will refer to these multigraphs as edge-coloured (or simply coloured) multigraphs. For examples illustrating these ideas, we refer the reader to Refs. [13,16]. 3 The extra structure of edge-coloured multigraphs will allow us to formalise the previous discussion concerning the more restrictive nature of the quantum probability assignments in Bell scenarios thanks to the following definition. Definition 7 An orthogonal projective representation (OPR) of a multigraph G= (V, E)composed of simple graphs GA= (V, EA), . . . , GN= (V, EN)is an assignment of a projector Πi= ΠA i⊗ · · · ⊗ ΠN i, where ⊗denotes tensor product, to each i∈Vsuch that {ΠJ i:i∈V}constitutes an orthogonal projective representation of GJ, for all parties (subsystems) J. Notice that an OPR of an edge-coloured multigraph Galso is an OPR of the graph constructed from Gby merging all the edges connecting each two vertices into a single (colourless) one. We refer to this simple graph as the shadow of the multigraph G. Therefore, the general question addressed in this work can be stated as follows: given a graph G, is there an OPR of an edge-coloured version of Gwhich is able to achieve its Lov´ asz number, thus being a Lov´ asz-optimal OPR of the shadow G? In other words, can the quantum maximum for a graph of exclusivity Gbe achieved in a Bell scenario? The answer to this question depends on the specific graph Gunder consideration. There are known examples illustrating both possibilities. The Clauser-Horne-Shimony-Holt Bell inequality, for instance, achieves its maximum quantum value in a Bell scenario. On the other hand, none of the edgecolourings of the pentagon reaches its colourless Lov´ asz number [13,17]. In this work, we analyse this question for a special class of graphs which includes the pentagon, the odd cycles with five or more vertices, and their complements (see Definition 9). Except for the pentagon, it remained unclear whether the quantum maxima for them could be achieved in Bell scenarios. The odd cycles with five or more vertices, called odd holes, and denoted by Cn, and their complements, called odd antiholes Cn, are quite important in the study of nonclassical correlations, in the light of the perfect graph theorem. Definition 8 A subgraph Hof a graph Gis an induced subgraph if, for any pair of vertices i, j of H,(i, j)is an edge of Hif and only if (i, j)is an edge of G. Definition 9 The complement of a graph G, denoted by G, is a graph with the same vertex set as Gand in which two different vertices are adjacent if and only if they are not adjacent in G. Theorem 2 [12,18] (The perfect graph theorem) If a graph Ghas no odd cycle with five or more vertices, nor their complements, as induced subgraphs, then α(G) = ϑ(G). In other words, if quantum theory violates a Bell or noncontextuality inequality, the graph of exclusivity of its associated witness must necessarily contain an induced odd hole or an induced odd antihole. In this sense, odd holes and odd antiholes of exclusivity constitute the building blocks of nonclassical correlations. III. RESULTS A. Quantum maxima for holes in Bell scenarios The colourless cycles have been extensively studied in literature. Indeed, we know an analytical expression for ϑ(Cn) for any odd n≥5[19–21]. Furthermore, the Lov´ aszoptimal OPRs of these cycles are very well characterised, and must satisfy some strong symmetry conditions, a result which comes from self-testing [22]. With this in mind, we can prove the following theorem. Theorem 3 There is no orthogonal projective representation of any coloured odd n-cycle, Cn, with n≥5, using at least two colours, which is a Lov´ asz-optimal representation of the shadow Cn. In other words, this can be expressed as the following corollary. Corollary 4 An odd hole cannot reach its quantum maximum in any Bell scenario. This was known to be the case for n= 5 [17]. However, it was an open problem for the other holes. This is the main contribution of this paper. Notice that Theorem 3holds for any edge-colouring of the odd holes. However, it is not true that every colouring can represent events of a Bell scenario. To continue our discussion, we first need to address this point. B. When does a coloured multigraph represent exclusivity relations between events in a Bell scenario? The following theorem completely characterises which kind of edge-coloured multigraph can represent events in a Bell scenario. Theorem 5 A coloured multigraph represents the relations of exclusivity between events in a Bell scenario if and only if the graph of each colour, c, is the disjoint union of mccomplete ojc-partite graphs, with jc= 1, . . . , mc. Each colour crepresents a party, mcis the number of measurements of the party represented by colour c, and ojcis the number of outputs of this party’s jc-th measurement. Definition 10 A graph G= (V, E)is a complete k-partite graph if Vis the disjoint union of knon-empty sets Vk, and two vertices, x, y, are adjacent if and only if x∈Vkand y∈Vlfor k=l. For example, Fig. 1presents four coloured graphs. Theorem 5allows us to rapidly conclude that only three of them can represent events in Bell scenarios. Complete k-partite graphs can be recognised in polynomial time even when the partition into kdisjoint sets (see previous definition) is not supplied. Recall that complete k-partite graphs are equivalent to ¯ P3-free graphs, the graphs such that 4 0,_|0,_ 1,0|0,1 _,1|_,1 1,0|1,1 0,0|1,0 _,1|_,0 1,0|0,0 0,_|0,_ 1,0|0,2 1,1|2,2 0,1|2,1 1,0|1,1 0,1|1,0 1,0|0,0 0,_,_|0,_,_ 1,0,_|0,1,_ _,1,0|_,1,1 1,_,1|1,_,1 0,_,1|1,_,0 _,1,0| _,0,0 1,0,_|0,0._ FIG. 1. (a), (b), and (c) are coloured graphs that represent the relations of exclusivity of events in, respectively, the (2,2,2),(2,3,2), and (3,2,2) Bell scenarios, where (p, m, o)indicates that there are pparties, each with mmeasurements, of ooutcomes. In contrast, (d) does not represent events in any Bell scenario, due to the red path of size 3.a, b|x, y denotes the event in which Alice measures xand obtains a, and Bob measures yand obtains b. Similarly, a, b, c|x, y, z denotes the event in which Alice measures xand obtains a, Bob measures yand obtains b, and Charlie measures zand obtains c. The “ ” on the labelings of some events means that the respective measurement is ignored. ¯ P3(the graph with 3 vertices and a single edge) is a forbidden subgraph. Recognition of such graphs can be done in polynomial time by means of finite forbidden subgraph characterisation. Therefore, Theorem 5provides a useful way of determining whether or not a given coloured multigraph can represent events in Bell scenarios. Moreover, it helps us to identify the simplest Bell scenario in which the coloured multigraph fits in and to find a libelling for the vertices. This is so because each component of each colour corresponds to a measurement on the respective part. The simplest building block would be a complete graph Ko with the respective number of outputs. Since the same local pair measurement-result commonly appears in more than one term of the Bell inequality, this gives rise to the classification in terms of complete o-partite graphs: each (maximal) independent set in this (connected) graph corresponds to a different outcome for the measurement specified by this component. Finally, this naturally defines the minimal Bell scenario in which such inequality fits. C. Quantum maxima for holes in bipartite Bell scenarios With the above characterisation, we can compute what is the quantum maxima for odd holes in bipartite Bell scenarios. Notice that Theorem 3, although valid for any edge-coloured odd hole, does not provide a way to compute their quantum maxima in Bell scenarios. Theorem 6 In bipartite Bell scenarios, the maximum quantum value for a graph of exclusivity Cn, with odd n≥5, is MB(Cn) = 1 2+(n−1) 41 + cos π n−1.(3) This maximum occurs in the (2,(n−1)/2,2) Bell scenario and corresponds to the maximum quantum violation of the chained Bell inequality with (n−1)/2measurements per party [19,20]. This contrasts with the well known result [21] ϑ(Cn) = ncos π n 1 + cos π n.(4) D. Quantum maxima for antiholes in Bell scenarios Finally, we now discuss the question of whether the quantum maxima of odd antiholes can be achieved in Bell scenarios. Analogously to Corollary 4, we believe in a similar result for odd antiholes, expressed as the following conjecture. Conjecture 7 An odd antihole (i.e., the complement of an odd hole) cannot reach its quantum maximum in any Bell scenario. That is, Corollary 4alongside with the above conjecture states that the basic structures responsible for the quantum versus classical difference, odd holes and antiholes, cannot reach their maximal quantum values when embedded into Bell scenarios. We know, however, that an exact analogous of Theorem 3 does not hold for odd antiholes, as we have found an edgecolouring of ¯ C7, shown in Fig. 4(a), which has an OPR achieving the Lov´ asz number of ¯ C7. It turns out, however, that this colouring cannot represent the events of a Bell scenario, according to Theorem 5. We thus believe in the following conjecture. Conjecture 8 There is no orthogonal projective representation of any Bell edge-coloured odd antihole ¯ Cnwhich is a Lov´ asz-optimal representation of the shadow ¯ Cn. Corollary 4follows from Theorem 3, as well as Conjecture 7follows from Conjecture 8. In the simplest case, n= 5, Conjecture 8comes from Theorem 3and the fact that C5is self-complementary. We thus prove it for the first important case, n= 7. Theorem 9 MB(¯ C7)< ϑ(¯ C7). The proof of this theorem will not be constructive. We actually do not know what is the maximum obtained for C7for Bell scenarios. On the other hand, the maximum that can be obtained without extra constraints in quantum theory is well known [15]. 5 IV. DISCUSSION How are our results related to the problem of finding the principle of nonlocal quantum correlations? In a nutshell, our results show how, even at the level of contextuality building blocks, the constraints inherent to any Bell scenario transform quantum sets that are easy to characterise (and follow from a simple principle) into quantum sets that are difficult even to bound. The set of quantum probability assignments for a graph of exclusivity Gis the set of probabilities for events having Gas graph of exclusivity, without specifying which scenario produces the events (all scenarios are valid). It can be proven [12] that, for any graph G, the set of quantum probability assignments is the theta body of G[23], which, for any G, is a closed set. Any element of the theta body of Gcan be achieved in the KS contextuality scenario consisting of dichotomic observables with a graph of compatibility isomorphic to G[15]. Moreover, given G, deciding whether a probability assignment is quantum or not is the solution of a single semi-definite program [23]. More importantly, there is a simple principle that, for any graph, selects the theta body [10]. In contrast to that, the set of quantum correlations (a correlation is a probability assignment for all the events produced in a scenario) for a given (Bell or KS) scenario is, in general, not closed [24], and the problem of whether a correlation is quantum or not is, in general, undecidable [24]. Moreover, the maximal quantum violation of a Bell inequality may not be computable. In fact, it may be even impossible to approximate [25,26]. All these features help us to understand why it is difficult to find a single principle that selects the quantum sets of correlations for Bell scenarios. These sets are much more difficult to characterise. Consequently, it is reasonable to expect that they are more difficult to understand. Interestingly, the set of quantum correlations for any scenario is a subset of the set of quantum probability assignments for the graph of exclusivity of all events in that scenario. Therefore, all difficulties arise when adding scenario constraints. That is why, for identifying the principle of quantum nonlocal correlations, it is useful to start by identifying the principle of quantum probability assignments for the graphs of exclusivity [10]. But it is also important to study the transition between the respective theta bodies and the corresponding sets of correlations and identify exactly where the difference between the sets begins. The results presented in this paper show that the differences (and the difficulties) already appear at the level of the simplest graphs of exclusivity. We have shown that, already there, the constraints of any Bell scenario exclude maximal quantum assignments. On the one hand, this stresses the importance of experimentally testing quantum maximally KS contextual correlations for holes and antiholes. They are fundamental predictions of quantum theory that no Bell test can target. For odd holes, beautiful experiments with repeatable and minimally disturbing measurements have been performed on ions [27]. However, for odd antiholes, so far, there are only photonic tests simulating sequential measurements [28]. It would be interesting to test the quantum maximum for antihole correlations with repeatable and minimally disturbing measurements. One difficulty of these experiments is that kantihole correlations require quantum systems of dimension k−2and sequences of (k−1)/2measurements [15]. On the other hand, our results leave some open questions whose answer may help us to better understand quantum theory and identify further applications. For example, (i) Is there a way to prove that, in Bell scenarios, the maximum quantum value for Cn, with odd n≥9, is strictly smaller than the maximum quantum value for Cn? (ii) What is the quantum maxima for odd antiholes in Bell scenarios? In which Bell scenarios do these maxima occur? (iii) Can we achieve the quantum maxima for odd holes and antiholes in hybrid scenarios where sequential local measurements are performed on parts of an entangled system [29–31]? And, if so, which tasks may take advantage of these correlations? Further research is needed to answer all these questions. V. PROOFS In this section, we present the proofs of the results stated in Sec. III. In some of them we will use a concept which is the analogous of the Lov´ asz number for edge-coloured multigraphs. Definition 11 [13] The factor-constrained Lov´ asz number of a multigraph Gcomposed of simple graphs GA= (V, EA), . . . , GN= (V, EN)is ϑc(G) := sup X i∈V ⟨ψ|Πi|ψ⟩,(5) where the supremum in the sum is taken over all orthogonal projective representations of G, unit vectors |ψ⟩in the D- dimensional Hilbert space of the OPR (not necessarily product vectors), and dimensions D(not necessarily finite). We say that an orthogonal projective representation of Gis Lov´ asz-optimal if it realises ϑc(G)for some handle. For simplicity, we will refer to ϑc(G)as the coloured Lov´ asz number of G. A. Proof of Theorem 3 To prove Theorem 3, our strategy will be to show that, for any edge-coloured Cnwith odd n≥5and containing at least two colours, no Lov´ asz-optimal OPR satisfies a symmetry property satisfied by all Lov´ asz-optimal OPRs of the shadow Cn, given by the following lemma. 6 Lemma 10 [22] Consider a Lov´ asz-optimal OPR of Cn, with odd n, and handle |ψ⟩such that ϑ(Cn) = Pi⟨ψ|Πi|ψ⟩, where Πiis the projector associated to vertex iin this OPR. Then, for every vertex i,pn=⟨ψ|Πi|ψ⟩=cos(π/n) 1+cos(π/n). (a) (b) FIG. 2. Induced subgraphs of edge-coloured cycles used to prove Lemma 12, (a), and Lemma 13, (b). Now, to prove Theorem 3in full generality, we would need, in principle, to deal with all possible edge-colourings of Cn. However, the following lemma greatly simplifies the colourings that we have to consider. Lemma 11 (Removing edges does not decrease the coloured Lov´ asz number) If Gis a coloured multigraph and His the coloured multigraph obtained from Gby removing an edge, then ϑc(H)≥ϑc(G). Proof: By definition, ϑc(G)is a maximisation of a sum over the vertices of G, with restrictions given by the edges of G. Since Hhas the same vertices as G,ϑc(H)is a maximisation of the same sum, with less restrictions (all edges of G except for the removed edge). Lemma 11 implies that, among all possible colourings of Cn, the one with largest coloured Lov´ asz number is one without multiple edges. Therefore, it suffices to prove Theorem 3 for the edge-coloured versions of Cncontaining only simple edges. Notice that, for any coloured Cnwith this property, that is, without multiple edges, each vertex is only connected to two edges. Thus, in any Lov´ asz-optimal OPR of these graphs, the projector associated to each vertex ican be written as Πi= ΠA i⊗IB⊗IC⊗ · · · ⊗ ΠJ i⊗IK⊗ · · · ⊗ IN= ΠA i⊗ΠJ i, where Aand Jare the parties associated to the colours of the edges vertex iis connected with. Moreover, whenever neighbouring edges have different colours, we might further simplify the projectors. Suppose, for instance, that vertex i−1and iare connected by an A coloured edge, and vertex iis connected to i+1 by an edge of a different colour. Then, for any Lov´ asz-optimal OPR, we can write ΠA i=IA−ΠA i−1. With these properties, we can prove the following lemmas. Lemma 12 Consider an edge-coloured Cn, with odd n, containing only simple edges and such that vertex i−1is connected to vertex iwith an edge of colour A, vertex iis connected to vertex i+ 1 with an edge of the same colour A, and the edge connecting i+ 1 and i+ 2 has a different colour B. See Fig. 2(a). If a Lov´ asz-optimal OPR of this coloured Cn achieves its colourless Lov´ asz number with handle |ψ⟩, then, in this OPR, vertices iand i+ 1 are associated to projectors Πi= ΠA i⊗Iand Πi+1 = (IA−ΠA i)⊗ΠB i+1 satisfying ⟨ψ|ΠA i⊗ΠB i+1|ψ⟩= 0. Proof: Without loss of generality, we can assume that in a Lov´ asz-optimal OPR of a coloured Cnsuch as described above, the projectors associated to vertices i−1,i,i+ 1, and i+ 2 can be written as Πi−1= ΠA i−1⊗ΠB...N i−1,Πi= ΠA i⊗I,Πi+1 = (IA−ΠA i)⊗ΠB i+1, and Πi+2 = (IB− ΠB i+1)⊗ΠAC...N i+2 , respectively, where ΠA i−1ΠA i= 0. If this representation achieves the colourless Lov´ asz number of Cn, then we also know by Lemma 10 that, for every vertex i, its associated projector satisfies ⟨ψ|Πi|ψ⟩=pn. Now, consider a similar projective representation of this graph, in which we only substitute Πiand Πi+1 for, respectively, Π′ i= ΠA i⊗(IB−ΠB i+1)and Π′ i+1 =I⊗ΠB i+1, while keeping the rest of the representation unchanged. This is not exactly an OPR of the considered edge-coloured graph, but notice that the projectors Πi−1,Π′ i,Π′ i+1, and Πi+2 satisfy Πi−1Π′ i= Π′ iΠ′ i+1 = Π′ i+1Πi+2 = 0. That is, this new representation is an OPR of the shadow Cn. Moreover, since Π′ i+ Π′ i+1 = Πi+ Πi+1, this OPR is Lov´ asz-optimal. Therefore, Lemma 10 guarantees that ⟨ψ|ΠA i⊗(IB−ΠB i+1)|ψ⟩= ⟨ψ|ΠA i⊗I|ψ⟩, which implies ⟨ψ|ΠA i⊗ΠB i+1|ψ⟩= 0. Lemma 13 Consider an edge-coloured Cn, with odd n, containing only simple edges and such that vertex i−1is connected to vertex iwith an Acoloured edge, vertex iis connected to i+ 1 with an edge of a different colour B, and vertex i+ 1 is connected to vertex i+ 2 with a Ccoloured edge, which is a different colour than B, but might be the same as A. See Fig. 2(b). Moreover, consider a Lov´ asz-optimal OPR with projectors Πi−1= ΠA i−1⊗ΠB...N i−1,Πi= (IA− ΠA i−1)⊗ΠB i, and handle |ψ⟩, satisfying ⟨ψ|ΠA i−1⊗ΠB i|ψ⟩= 0 and ⟨ψ|ΠA i−1⊗I|ψ⟩=pn. Then, if this representation achieves the colourless Lov´ asz number of Cn, the projector Πi+1 = (IB−ΠB i)⊗ΠC i+1 is such that ⟨ψ|ΠB i⊗ΠC i+1|ψ⟩= 0. Proof: The proof is completely analogous to the proof of Lemma 12. First, notice that we can substitute Πi= (IA− ΠA i−1)⊗ΠB ifor Π′ i=I⊗ΠB i, and then jointly substitute Π′ iand Πi+1 = (IB−ΠB i)⊗ΠC i+1 for Π′′ i= ΠB i⊗(IC− ΠC i+1)and Π′′ i+1 =I⊗ΠC i+1, respectively. These changes do not alter the sum Pi⟨ψ|Πi|ψ⟩, so we still get a Lov´ aszoptimal OPR of the shadow Cnwith the same construction used in Lemma 12. Then, by using Lemma 10, one can obtain ⟨ψ|ΠB i⊗ΠC i+1|ψ⟩= 0. These lemmas tell us how to propagate projectors along a cycle. Suppose that there exists an OPR of a coloured version of Cn, with odd nand without multiple edges, achieving its colourless Lov´ asz number. Moreover, suppose that in this graph there exists a path of at least size two which ends, say, in vertex 2. Let Abe the colour of this path and Bbe the colour of the edge connecting vertices 2and 3. Then, we know that Π1= ΠA 1,Π2= (I−ΠA 1)⊗ΠB 2, and Lemma 12 guarantees that ⟨ψ|ΠA 1⊗ΠB 2|ψ⟩= 0. If the edge connecting vertices 3and 4also has the colour B, then we can write Π3=I−ΠB 2. However, since this is an OPR achieving the colourless Lov´ asz number of Cn, by Lemma 10 we have pn=⟨ψ|ΠB 2|ψ⟩=⟨ψ|(I−ΠB 2)|ψ⟩= 1−pn, that is, pn= 1/2. This is in contradiction with the fact that pn=cos(π/n) 1+cos(π/n)<1/2. 7 FIG. 3. Coloured multigraphs corresponding to events in the Bell scenario (2,(n−1)/2,2) and providing the maximum quantum Bell nonlocal value for holes. a, b|x, y denotes the event in which Alice measures xand obtains a, and Bob measures yand obtains b. The “ ” on the labelings of some events means that the respective measurement is ignored. On the other hand, if the edge connecting 3and 4is of a different colour than B, then we can successively apply Lemma 13 until we find a path of at least size two, in which, once more, the contradiction described above occurs. In the worst case, this path will be the one we started with. The proof is almost complete, but there is a gap yet to be filled, which is the fact that not all coloured Cn’s have a path of at least size two, a necessary ingredient for the above reasoning. However, the following lemma says that, if this path does not exist, we can construct one. Lemma 14 (Merging colours) If Gis a coloured graph with qcolours, and His the (q−1)-coloured graph obtained from Gby merging two colours, then ϑc(H)≥ϑc(G). Proof: Any valid OPR for Ginduces an OPR for Hwhen we consider for the merged colours the tensor product of their vector spaces as just one factor. If a coloured Cn, with nodd and without multiple edges, has only two colours, then there always exists a path of at least size two. If there are more colours and there is no such path, then Lemma 14 allows us to simply merge two of the colours in order to construct it. This concludes the proof of Theorem 3. B. Proof of Theorem 5 Let us start from a given Bell scenario. A Bell inequality can be written as a weighted sum of probabilities of events aI|AI, where Iis the list of parts making measurements for this event, AIis the ordered list of measurements chosen for each part, and aIis the corresponding list of outputs. Those events correspond to the vertices of the coloured graph. Two vertices aI|AIand bJ|BJare linked in the colour ccorresponding to some part whenever this part cappears in Iand J, with Ac=Bc, while ac=bc. Let us now focus on the simple graph of colour c. Each measurement Min part cgives rise to one piece (component) of this graph (notice that a measurement will only appear as a component of the graph if at least two different outputs appear in different events in the inequality). Events with different outputs for the same measurement are always connected. Since there can be different events with the same output for Min part c, this says that this piece is not necessarily a complete graph, but characterises it as a complete oM-partite graph, where oMis the number of different outputs for Mappearing at this inequality. This proves one side of the assertion. The other side of the assertion was explained and essentially proved in Sect. III. Given a coloured graph in which each colour cis the disjoint union of mccomponents, each of them an ojc-complete graph, each vertex will be labelled as aI|AI, where Ilists the colours for which there is some edge incident on it, and for each piece for each colour, a label is chosen for a measurement, while each independent set in this piece receives a label for an output. C. Proof of Theorem 6 To prove Theorem 6, we only need to consider two-colour edge-coloured Cn, since we are only concerned with bipartite Bell scenarios. Also, because of Lemma 11, we need to consider only graphs without multiple edges. Then, to begin with, we prove a lemma which is useful to simplify even further the graphs we have to analyse. It allows us to transform coloured cycles into simpler ones while keeping track of the changes in their coloured Lov´ asz number. Lemma 15 Consider an edge-coloured n-cycle Cn, without multiple edges, and such that the edges {i−1, i},{i, i + 1} and {i+ 1, i + 2}are all of the same colour A, and the edges {i−2, i −1}and {i+ 2, i + 3}are not of the colour A. Then, consider the graph Cn−2which is constructed from Cn by excluding the vertices iand i+ 1 and connecting vertices i−1and i+ 2 with an edge of colour A. Then, ϑc(Cn) = ϑc(Cn−2)+1. Proof: Consider a Lov´ asz-optimal OPR of the graph Cn. Without loss of generality, we can assume Πi−1= (IA− ΠA i)⊗ΠB i−1,Πi= ΠA i,Πi+1 = ΠA i+1 and Πi+2 = (IA− ΠA i+1)⊗ΠC i+2. However, we know that ΠA i+1 ≤IA−ΠA iand, moreover, for whatever projectors ΠAand ΠC, it holds that ΠA⊗IC≥ΠA⊗ΠC. Therefore, we can take ΠA i+1 =IA− ΠA i. This leads to an OPR whose restriction to all the vertices of Cn, except iand i+ 1, is also an OPR of the graph Cn−2. Now, given that Πi+ Πi+1 =I, it follows that ϑc(Cn) = ϑc(Cn−2)+1. We can combine this Lemma with the ideas used to proof Lemma 12 to prove the following. Lemma 16 Consider two coloured cycles Cnand Cn−2, without multiple edges, such that Cnis constructed from Cn−2by creating a vertex i′between the vertices iand i+ 1 of Cn−2, creating two new edges {i, i′}and {i′, i + 1}of the same colour of the edge {i, i + 1}, and removing this edge. To complete the construction of Cn, this procedure is repeated in any other edge {j, j + 1}of Cn−2. Then, ϑc(Cn) = ϑc(Cn−2)+1. 8 FIG. 4. Coloured multigraphs used in the proof of Theorem 9. Proof: Notice that the idea of changing the OPR in a size two path just like described in the proof of Lemma 12 is equivalent to changing the colouring of the cycle in such a way as to move the size two path along the graph. One can then take Cn into a different edge-coloured graph which is related to Cn−2 in the same way as described on Lemma 15. Now, taking into account Theorem 5, a Bell colouring of a cycle cannot have a path of size three or larger. Thus, a Bell colouring of a cycle only contains paths of size one or two. Moreover, given that we are restricted to two colours, an odd cycle must contain an odd number of paths of size two (as well as an odd number of paths of size one). So, in the first place, consider an odd edge-coloured hole Cnwith only one size-two path. One can verify that the only event assignments consistent with this exclusivity structure gives rise to an inequality which is a re-scaled and shifted chained inequality. Fig. 3shows three coloured multigraphs corresponding to events in the Bell scenario (2,(n−1)/2,2) [19–21]. The quantum maximum of a chained inequality is well known [32], and we can use it to conclude that ϑc(Cn) = 1 2+(n−1) 41 + cos π n−1.(6) More generally, if Cnhas tpaths of size two, it is possible to use Lemma 16 to reduce it to an odd hole with only one path of size two, while taking into account the unit changes in the coloured Lov´ asz number. Thus, in this case, ϑc(Cn) = t 2+n−t 41 + cos π n−t.(7) The maximum of this expression is attained when t= 1, and thus the proof is concluded. D. Proof of Theorem 9 We begin by computing the factor-constrained Lov´ asz number for all possible ways of colouring C7with two colours. We observe that there is only one way such that ϑc(C7) = ϑ(C7); this colouration is presented in Fig. 4(a), where C7is ‘factored’ into two C7’s, coloured distinctively (note that this colouring does not represent a set of events of a Bell scenario). Suppose that one wants to try to obtain this value in a Bell scenario. The merging colours Lemma 14 implies that it would be necessary to obtain this specific two-colouring whenever merging colours into two sets. Let us focus just on one factor. As a C7, it can be Bell-coloured in many ways, for example, as in Fig. 4(b). However, this allows for other colour merging, merging some of the new colours to the one of the other previous C7factor, like in Fig. 4(c). This contradiction shows that any Bell coloured C7will necessarily have ϑc(C7)< ϑ(C7). Another way of phrasing the above proof is that, since the only bi-colouring that reaches ϑ(C7)is not Bell, more colours will be needed. By merging colours, different upper bounds will be given by each bi-coloured C7obtained in the process. Naturally, in the end, the smaller upper bound over all merging colours processes is the relevant one. Since every other bicolouring implies ϑc(C7)< ϑ(C7), no Bell colouring of C7 can reach ϑ(C7). ACKNOWLEDGMENTS We thank J. R. Portillo for useful conversations. This work was supported by the program Science without Borders (CAPES and CNPq), by the S˜ ao Paulo Research Foundation FAPESP (grants nos. 2018/07258-7 and 2023/04197- 5), by C´ atedras Ibero-Americanas (Banco Santander, Call 062/2017), by CNPq under grant no. 310269/2019-9, by the QuantERA grant SECRET, by MCINN/AEI (project no. PCI2019-111885-2) and by MCINN/AEI (project no. PID2020-113738GB-I00). [1] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419 (2014). [2] S. Popescu and D. Rohrlich, Quantum nonlocality as an axiom, Found. Phys. 24, 379-385 (1994). [3] J. A. Wheeler, How come the quantum?, Ann. N. Y. Acad. Sci. 480, 304-316 (1986). [4] M. Pawłowski, T. Paterek, D. Kaszlikowski, V. Scarani, A. Winter, and M. ˙ Zukowski, Information causality as a physical principle, Nature 461, 1101-1104 (2009). [5] M. Navascu´ es and H. Wunderlich, A glance beyond the quantum model, Proc. R. Soc. A 466, 881-890 (2010). [6] T. Fritz, A. B. Sainz, R. Augusiak, J. B. Brask, R. Chaves, A. Leverrier, and A. Ac´ ın, Local orthogonality as a multipartite principle for quantum correlations, Nature Comm. 4, 2263 (2013). [7] A. B. Sainz, Y. Guryanova, A. Ac´ ın, and M. Navascu´ es, Almost quantum correlations violate the no-restriction hypothesis, Phys. Rev. Lett. 120, 200402 (2018). [8] A. Cabello, The problem of quantum correlations and the totalitarian principle, Philos. Trans. R. Soc. A 377, 2019.0136 (2019). [9] C. Budroni, A. Cabello, O. G¨ uhne, M. Kleinmann, and J.- ˚ A. Larsson, Kochen-Specker contextuality, Rev. Mod. Phys. 94, 045007 (2022). [10] A. Cabello, Quantum correlations from simple assumptions, Phys. Rev. A 100, 032120 (2019). 9 [11] A. Cabello, S. Severini, and A. Winter, (Non-)Contextuality of physical theories as an axiom, arXiv:1010.2163. [12] A. Cabello, S. Severini, and A. Winter, Graph-theoretic approach to quantum correlations, Phys. Rev. Lett. 112, 040401 (2014). [13] R. Rabelo, C. Duarte, A. J. L´ opez-Tarrida, M. Terra Cunha, and A. Cabello, Multigraph approach to quantum non-locality, J. Phys. A: Math. Theor. 47, 424021 (2014). [14] B. Amaral and M. Terra Cunha, On Graph Approaches to Contextuality and their Role in Quantum Theory (Springer Nature, Switzerland, 2018). [15] A. Cabello, L. E. Danielsen, A. J. L´ opez-Tarrida, and J. R. Portillo, Basic exclusivity graphs in quantum correlations, Phys. Rev. A 88, 032104 (2013). [16] L. Vandr´ e and M. Terra Cunha, Quantum sets of the multicolored-graph approach to contextuality, Phys. Rev. A 106, 062210 (2022). [17] M. Sadiq, P. Badzia¸g, M. Bourennane, and A. Cabello, Bell inequalities for the simplest exclusivity graph, Phys. Rev. A 87, 012128 (2013). [18] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164, 51-229 (2006). [19] P. M. Pearle, Hidden-variable example based upon data rejection, Phys. Rev. D 2, 1418 (1970). [20] S. L. Braunstein and C. M. Caves, Wringing out better Bell inequalities, Annals of Physics 202, 22 (1990). [21] M. Ara´ ujo, M. T. Quintino, C. Budroni, M. Terra Cunha, and A. Cabello, All noncontextuality inequalities for the n-cycle scenario, Phys. Rev. A 88, 022118 (2013). [22] K. Bharti, M. Ray, A. Varvitsiotis, N. A. Warsi, A. Cabello, and L.-C. Kwek, Robust self-testing of quantum systems via noncontextuality inequalities, Phys. Rev. Lett. 122, 250403 (2019). [23] M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver, Relaxations of vertex packing, J. Combin. Theory B 40, 330-343 (1986). [24] W. Slofstra, The set of quantum correlations is not closed, Forum Math. Pi 7, E1 (2019). [25] Z. Ji, Compression of quantum multi-prover interactive proofs, STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Association for Computing Machinery, New York, NY, 2017), pp. 289-302. [26] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, MIP*=RE, Comm. ACM 64, 131 (2021). [27] M. Malinowski, C. Zhang, F. M. Leupold, A. Cabello, J. Alonso, and J. P. Home, Probing the limits of correlations in an indivisible quantum system, Phys. Rev. A 98, 050102(R) (2018). [28] M. Arias, G. Ca˜ nas, E. S. G´ omez, J. F. Barra, G. B. Xavier, G. Lima, V. D’Ambrosio, F. Baccari, F. Sciarrino, and A. Cabello, Testing noncontextuality inequalities that are building blocks of quantum correlations, Phys. Rev. A 92, 032126 (2015). [29] P. Kurzy´ nski, A. Cabello, and D. Kaszlikowski, Fundamental monogamy relation between contextuality and nonlocality, Phys. Rev. Lett. 112, 100401 (2014). [30] T. Temistocles, R. Rabelo, and M. Terra Cunha, Measurement compatibility in Bell nonlocality tests, Phys. Rev. A 99, 042120 (2019). [31] P. Xue, L. Xiao, G. Ruffolo, A. Mazzari, T. Temistocles, M. Terra Cunha, and R. Rabelo, Synchronous observation of Bell nonlocality and state-dependent contextuality, Phys. Rev. Lett. 130, 040201 (2023). [32] Stephanie Wehner, Tsirelson bounds for generalized Clauser- Horne-Shimony-Holt inequalities, Phys. Rev. A 73, 022110 (2005)