Quantum contextuality provides communication complexity advantage

Quantum Contextuality Provides Communication Complexity Advantage Shashank Gupta ,1Debashis Saha ,1,2 Zhen-Peng Xu,3,4 Adán Cabello,5,6 and A. S. Majumdar1 1S. N. Bose National Centre for Basic Sciences, Block JD, Sector III, Salt Lake, Kolkata 700106, India 2School of Physics, Indian Institute of Science Education and Research Thiruvananthapuram, Kerala 695551, India 3School of Physics and Optoelectronics Engineering, Anhui University, 230601 Hefei, People’s Republic of China 4Naturwissenschaftlich-Technische Fakultät, Universität Siegen, Walter-Flex-Straße 3, 57068 Siegen, Germany 5Departamento de Física Aplicada II, Universidad de Sevilla, E-41012 Sevilla, Spain 6Instituto Carlos I de Física Teórica y Computacional, Universidad de Sevilla, E-41012 Sevilla, Spain (Received 30 June 2022; accepted 31 January 2023; published 24 February 2023) Despite the conceptual importance of contextuality in quantum mechanics, there is a hitherto limited number of applications requiring contextuality but not entanglement. Here, we show that for any quantum state and observables of sufficiently small dimensions producing contextuality, there exists a communication task with quantum advantage. Conversely, any quantum advantage in this task admits a proof of contextuality whenever an additional condition holds. We further show that given any set of observables allowing for quantum state-independent contextuality, there exists a class of communication tasks wherein the difference between classical and quantum communication complexities increases as the number of inputs grows. Finally, we show how to convert each of these communication tasks into a semi-device- independent protocol for quantum key distribution. DOI: 10.1103/PhysRevLett.130.080802 Introduction.—Contextuality is one of the most significant properties of quantum mechanics [1–6]. It stipulates that, for some correlations, there is no probability distribution in agreement with the marginal distributions corresponding to sets of compatible (i.e., jointly measurable) observables. In particular, contextuality forbids us to assign predetermined context-independent values to the outcomes of quantum sharp measurements (defined as those that yield the same outcome when they are repeated and do not disturb any compatible observable). While nonlocality, which can be seen as a form of quantum contextuality requiring entanglement, has found many applications in quantum communication [7–9], so far, entanglement unassisted quantum contextuality has found few applications despite its conceptual importance [10–19]. Here, we first show that any contextual correlations achieved using quantum systems of sufficiently small dimensions offer a quantum advantage in a suitably designed one-way communication complexity (or distributed computation) task. Conversely, whenever an additional condition holds, any quantum protocol providing advantage in those tasks produces a proof of contextuality. By itself, this result provides an operational way to understand the sense in which some famous forms of quantum contextuality (notably, the one produced by the violation of the Klyachko-Can-Binicioğlu-Shumovsky inequality with quantum systems of dimension three [3]) are “nonclassical.” As a second result, we show that for every form of stateindependent (SI) contextuality [4,24–26], the ratio between the dimensions of the classical systems and quantum systems required to accomplish the task can be made arbitrarily large by increasing the number of inputs. These communication complexity tasks are the so-called “equality problems”that appear in many practical scenarios [27–29]. Finally, we present a semi-device-independent protocol for quantum key distribution (QKD) [30], based on the quantum advantage in our communication complexity tasks, in which security is proven by using the monogamy relation [31–33] of contextuality. Contextuality witnesses.—Given a set feign i¼1of events produced in a contextuality experiment, one can define an n-vertex graph Gin which each event is represented by a vertex and exclusive events correspond to adjacent vertices. Gis called the graph of exclusivity of feign i¼1. In quantum mechanics, each event eiis represented by a projector Πi. Mutually exclusive events are represented by mutually orthogonal projectors. A quantum realization of a set of events feign i¼1with graph of exclusivity Gis a set of projectors fΠign i¼1that satisfies all the exclusivity relations in Gand all the constraints imposed by the definition of the events. Definition 1: Contextuality witness.—A functional W¼X n i¼1 wiPðeiÞ;ð1Þ where wi≥0and PðeiÞis the probability of event ei,isa quantum contextuality witness if there is a quantum realization fΠign i¼1of feign i¼0and a quantum state ρ PHYSICAL REVIEW LETTERS 130, 080802 (2023) 0031-9007=23=130(8)=080802(6) 080802-1 © 2023 American Physical Society such that X n i¼1 witrðρΠiÞ>αðG;  wÞ;ð2Þ where αðG;  wÞis the independence number of the vertexweighted graph ðG;  wÞ, where Gis the graph of exclusivity of feign i¼0and  w¼fwign i¼1. That is, αðG;  wÞis the largest value of Pi∈Iwi, where Iis the set of the subsets consisting of nonadjacent vertices of G[34]. The name “contextuality witness”follows from the fact that, given W, one can find a noncontextuality inequality [35,36] whose upper bound for noncontextual models is αðG;  wÞand whose quantum value is the lefthand side of Eq. (2) [5,35,36]. We will focus on quantum realizations of contextuality witnesses constructed as follows. We first identify a vertex-weighted graph ðG;  wÞfor which we can identify fΠign i¼1and ρsuch that Eq. (2) holds. We will refer to fðG;  wÞ;fΠign i¼1;ρgas a quantum realization of a contextuality witness for ðG;  wÞ. In some cases, there is no need to identify a state ρ. Definition 2: State-independent contextuality witness.— The functional Eq. (1) is a quantum state-independent contextuality witness for dimension dif there is a quantum realization fΠign i¼1of feign i¼0such that Eq. (2) holds ∀ρ∈OðCdÞ, where OðCdÞdenotes the set of quantum states in Cd. If we have fðG0; wÞ;fΠign0 i¼1;ρgsatisfying Eq. (2) that includes projectors that are not of rank one, we can obtain fðG;  wÞ;fjψiihψijgn i¼1;ρgsatisfying Eq. (2) by splitting each of the projectors that are not rank one into rank-one projectors. See Ref. [37], Appendix A. One-way communication complexity.—Communication complexity [27] studies the amount of communication required for tasks involving inputs distributed among several parties. In one-way communication complexity [8,27,38,39], there are two parties. As shown in Fig. 1, in each round, Alice, receives a random input x∈X. Depending upon x, Alice sends a message (classical or quantum) to Bob. In addition, Bob receives a random input y∈Y. Using yand the message received from Alice, Bob outputs z, which is Bob’s guess about a certain function fðx; yÞ. After many rounds, they produce the probability pðzjx; yÞof z, given inputs xand y. The figure of merit of the task is given by S¼X x;y tðx; yÞpðz¼fðx; yÞjx; yÞ;ð3Þ where tðx; yÞ≥0and Px;y tðx; yÞ¼1. We are interested in two aspects: first, the maximum value of Sthat can be achieved under the restriction that the dimension of the (classical or quantum) system communicated from Alice to Bob is d, and second, the minimum dimensional (classical or quantum) system required to communicate in order to achieve a certain value of S. Sharing prior classical randomness between Alice and Bob is allowed. Communication complexity advantage based on quantum contextuality witnesses.—Consider fðG;  wÞ; fjψiihψijgn i¼1;ρgsatisfying Eq. (2) andsuch that ρ∈OðCdÞ. Since wi≥0, without loss of generality, we can take maxiwi¼1. The task is defined as follows. First, we consider an extended graph ˜ Gby adding additional vertices toGsuch that each vertex in ˜ Gbelongs to,at least, one clique of size d. A clique is a set of vertices in which every pair is adjacent. We thereupon assign additional vectors (or rankone projectors) to those additional vertices, so each vector belongs to at least one basis within the new set of vectors; see Fig. 1. Alice receives x∈f0;1;…;nþkgand Bob receives y∈f1;…;nþkg, where knumber of vertices is added. Bob outputs his guess for fðx; yÞ¼8 > < > : 0;if y¼x; 1;if y∈Nx; 0;if y∈f1;…;ngandx¼0;ð4Þ where Nxis the set of the vertices that are adjacent to (i.e., neighborsof)xin ˜ G.Inotherwords,Bobneedstodistinguish the runs where y¼xandx¼0from the runs where y∈Nx. Except for these, whenever y≠xand y∉Nxor x¼0and y∈fnþ1;…;nþkg, the runs do not contribute to the figureofmeritofthecommunicationtask.Thatis,thetaskfor Alice and Bob is to maximize Sð ˜ G;  w;dÞ¼1 NX nþk x¼1 pðz¼0jx; y ¼xÞ þX nþk x¼1X y∈Nx pðz¼1jx; yÞ þX n y¼1 wypðz¼0jx¼0;yÞ;ð5Þ where FIG. 1. On the left, the construction of the extended graph from the 5-cycle graph. Each of the 8 vertices of the extended graph belongs to at least one clique of size 3. On the right, scheme of the communication complexity task based on the extended graph. PHYSICAL REVIEW LETTERS 130, 080802 (2023) 080802-2 N¼nþkþX nþk x¼1jNxjþX n i¼1 wi;ð6Þ thus Px;y tðx; yÞ¼1. Alice and Bob must accomplish this task with the restriction that the dimension of the (classical or quantum) system communicated between them is d. Therefore, the communication task is fully specified by the value of d, the extended graph ˜ G, and the weights  w.The important point is that there is quantum advantage in this communicationtask wheneverdis “sufficiently small”in the sense that d≤χðGÞ, where χðGÞis the chromatic number of the graph G[40]. Result 1.—For any fðG;  wÞ;fjψiihψijgn i¼1;ρgwith ρ∈ OðCdÞsuch that Eq. (2) holds and d≤χðGÞ, there exists a quantum strategy for the communication complexity task defined by Eq. (5) that provides an advantage over any strategy in which the system communicated between Alice and Bob is classical. In a general quantum strategy, let ρx∈OðCdÞdenote the quantum state sent by Alice to Bob upon receiving x, and let fM0jy;M1jy¼1−M0jygnþk y¼1denote the quantum measurement Bob performs on ρxto obtain z, upon receiving input y. Suppose that fðG;  wÞ;fjψiihψijgn i¼1;ρgis a contextuality witness satisfying Eq. (2). Since, the projectors in fjψiihψijgn i¼1are of rank one, one can always add krankone projectors fjψiihψijgnþk i¼nþ1so that the extended set fjψiihψijgnþk i¼1has the relations of orthogonality given by ˜ G. Given fðG;  wÞ;fjψiihψijgn i¼1;ρg, Alice and Bob choose an extended set and apply the following strategy: ρ0¼ρ;ρx¼jψxihψxj;x¼1;…;nþk; M0jy¼jψyihψyj;y¼1;…;nþk: ð7Þ This way, pðz¼0jx; y ¼xÞ¼pðz¼1jx; y ∈NxÞ¼1, so the value of Sð ˜ G;  w;dÞin Eq. (5) is 1 NnþkþX nþk x¼1jNxjþX n i¼1 witrðρjψiihψijÞ;ð8Þ while communicating a (quantum) system of dimension d between Alice and Bob. In contrast to that, we find the following. Theorem 1.—Whenever d≤χðGÞ, for any strategy in which the system communicated between Alice and Bob is a classical system of dimension d, the value of Sð ˜ G;  w;dÞis upper bounded by Sð ˜ G;w;dÞ≤Sð ˜ G;  w;dÞ c¼1 NnþkþX nþk x¼1jNxjþαðG;  wÞ−δ; ð9Þ where δis the minimum number of “improperly colored” vertices of ˜ Gwhen dcolors are used to color all the vertices. Avertex is improperly colored if it has at least one neighbor sharing the same color. For a proof, see Ref. [37], Appendix B. Because of Eq. (2) and the fact that δis non-negative, the expression in Eq. (8) is strictly larger than Sð ˜ G; w;dÞ c. Let us suppose that dmin is the minimum dimension in which the set of projectors fjψiihψijgand ρcan be realized such that fðG;  wÞ;fjψiihψijgn i¼1;ρgis a contextuality witness.For any SI contextuality witness,χðGÞ>d min [41–43]. Therefore, whenever d¼dmin, there will be at least two adjacent vertices sharing the same color when dcolors are used to color the graph, implying δ≥2. Moreover, in this case, ρ0can be any quantum state in OðCdÞ. Explicit examples of the quantum advantage for communication complexity tasks based on some quantum SI contextuality sets are presented in [37], Appendix D, together with a proof of their robustness against white noise. Certifying contextuality witness from communication complexity task.—The quantum communication strategy given by Eq. (7) is based on a contextuality witness. However, a general quantum strategy with advantage consists of a set of states fρxgnþk x¼0acting on Cdand a set of measurement fM0jygnþk y¼1so that the value of Sð ˜ G; w;dÞis greater than Sð ˜ G;  w;dÞ c. In general, such a strategy may not be related to contextuality witnesses. Nevertheless, the following theorem allows us to identify whether or not an unknown quantum communication strategy admits a contextuality witness. Theorem 2.—For the above introduced communication task defined by Sð ˜ G;  w;dÞ, the following condition holds: ∀x;y;pð0jx;y ¼xÞ¼pð1jx;y ∈NxÞ¼1;ð10Þ if and only if fρxgis a set of rank-oneprojectors that has ˜ Gas graph of orthogonality and ρx¼M0jx. For a proof, see Ref. [37], Appendix B. Therefore, Theorem 2 presents operational criteria to certify a set of rank-one projectors satisfying orthogonality relations according to a graph. Note that the probabilities in the Eq. (10) condition are the first two terms of Sð ˜ G;  w;dÞ. Consider the particular case of the task, Eq. (5), in which d¼χðGÞand an unknown quantum strategy comprising fρxg,fM0jygprovides greater value than Sð ˜ G; w;dÞ c. First, it follows from Eq. (9) that, in this case, Pn y¼1wytrðρ0M0jyÞ>αðG;  wÞsince δ¼0. In addition to that, if the first two terms in Sð ˜ G; w;dÞattain their algebraic values, then Theorem 2 implies fðG;  wÞ;fM0jygn y¼1;ρ0g must be a contextuality witness. Increasing advantage in communication complexity.— Here, we will consider only those contextuality witnesses where χðGÞ>d min. In these cases, it suffices to consider a simplified version of the above-described communication PHYSICAL REVIEW LETTERS 130, 080802 (2023) 080802-3 complexity task by taking the first two terms of Sð ˜ G;  w;dÞ. Therefore, the figure of merit will be SG¼1 NX n x¼1 pðz¼0jx; y ¼xÞþX n x¼1X y∈Nx pðz¼1jx; yÞ; ð11Þ where N¼nþPn x¼1jNxj. Here, the communication problem is solely based on the exclusivity graph G[15], and we do not need to consider additional inputs apart from the set of vertices of G. More importantly, this is an equality problem as Bob guesses whether his input yis equal to xor not [27]. Let QðGÞ[or CðGÞ] be the minimum dimension of quantum system (or classical system) that should be communicated to achieve SG¼1. We are now interested in quantum advantages in terms of CðGÞand QðGÞ.A quantum advantage in communication complexity implies CðGÞ>QðGÞ, or, equivalently, log2½CðGÞ >log2½QðGÞ conventionally expressed in terms of classical and quantum bits. Theorem 3.—Given any witness fðG;  wÞ; fjψiihψijgn i¼1;ρgwhere jψii∈Cdmin , QðGÞ≤dmin;CðGÞ¼χðGÞ:ð12Þ Moreover, QðGÞis the minimum dimension dsuch that there exists a set of projectors fΠigacting on Cdsatisfying the orthogonality relations given by G. A proof is provided in [37], Appendix B. We can readily check that the quantum strategy, ρx¼M0jx¼jψiihψij, yields SG¼1. Thus, we have an advantage whenever χðGÞ>d min. In order to observe an increasing advantage, we need to consider products of graphs. Definition 3: Inclusive graph product or co-normal product or disjunctive product or OR product G×H.— The vertex set of the “inclusive graph product”of two graphs G,His VðGÞ×VðHÞ. The edges of G×Hare defined as ði; jÞ∼ði0;j 0Þif and only if i∼jor i0∼j0.We denote by Gmthe m-times product of the same graph G[44,45]. Theorem 4.—Given a graph Gwith nvertices, the ratio between classical and quantum communication complexities of SGbased on Gm, that is, CðGmÞ=QðGmÞ, increases polynomially with m, CðGmÞ QðGmÞ≥χfðGÞ dmin m ;for m∈N;ð13Þ where χfðGÞis the fractional chromatic number of G[42]. For any graph, χfðGÞ≤χðGÞ. For a proof, see Ref. [37], Appendix B. Since χfðGÞ=dmin >1for any quantum SI contextuality set in dimension dmin [42,43], the right-hand side of Eq. (13) can be arbitrarily large as mincreases [46]. It follows from Eq. (13) that the difference between the classical and quantum complexities for the equality task based on Gm is lower bounded by m· log2ðχfðGÞ=dminÞbits, which increases with m. In Table I, we present some explicit examples of the quantum advantage. Before proceeding to the next section, we point out an example of SI witness and the respective equality problem where the separation between the classical and quantum communication complexities grows exponentially with the dimension. Consider the set of vectors in Cdof the form ð1=ffiffiffi d pÞ½1;ð−1Þx1;…;ð−1Þxd−1T, where xi∈f0;1gsuch that in every vector the number of xitaking value 1 is even. Note that there are 2d−2such vectors in Cd, and let us denote this set by fjϕiig2d−2 i¼1. The graph, say GNd, representing the orthogonality relations for this set of vectors was introduced by Newman [50] and has been recently studied in the context of application of contextuality [49]. It turns out for any d≥1128 and divisible by 4, fðGNd; wÞ;fjϕiihϕijgg is SI contextuality witness where wi¼1for all i(see Appendix C in [37] for the proof). Remarkably, for the equality problem defined by Eq. (11) with respect to GNd,wehave CðGNdÞ QðGNdÞ≥1 d2 1.99d :ð14Þ Thus, the gap between classical and quantum complexities is at least 0.007d−log2dbits. The detailed proof of this fact is provided in Appendix C of [37], which follows from the results by Frankl-Rödl [51]. Semi-device-independent quantum key distribution.— Here, we propose a QKD protocol based on quantum advantage in the communication complexity task introduced by Sð ˜ G;  w;dÞin Eq. (5) where dis taken to be dmin. Unlike fully device-dependent protocols [14,52], our protocol is semi-device-independent [30] involving two black boxes: Alice’s preparation device and Bob’s measurement device. We only assume that (i) the dimension of the TABLE I. In order to compare the quantum advantages originated from various SI contextuality witnesses, we have taken the value of mfor each set such that 200 qubits is sufficient to accomplish the respective equality problem. With respect to that, the lower bounds on the classical and quantum ratios have been obtained for various SI contextuality witnesses. SI witness with nd min χfðGÞ CðGmÞ=QðGmÞfrom Eq. (13) so that dm min ∼200 qubits YO-13 [25] 335=11 ≥6×1013 Peres-33 [47] 313=4≥4×1013 CEG-18 [48] 49=2≥3.4×107 Pauli-240 [49] 815 ≥1.9×1018 Pauli-4320 [49] 16 60 ≥5×1028 PHYSICAL REVIEW LETTERS 130, 080802 (2023) 080802-4 degrees of freedom (of the physical system), in which the information is encoded, is bounded by dmin, and (ii) the devices may share classical randomness but that is uncorrelated with the choices of the inputs x,y. The QKD protocol is as follows. After completing a large number of runs, Alice randomly chooses some runs and publicly announces her input xso that Bob can verify that the obtained value of the figure of merit is greater than Sc. Thereby, Bob is ensured that the probabilities produced by his device cannot be simulated by classical systems under the aforementioned assumptions. Bob publicly announces his input yfor the remaining runs. Subsequently, Alice notes down fðx; yÞaccording to Eq. (4) as the shared key. Whenever y∉fx; Nxg,or,y∈fnþ1;…;nþkgand x¼0, Alice publicly announces that the transmission is unsuccessful. It is not difficult to show that such QKD protocol is secure against restricted eavesdroppers whenever the contextuality witness satisfies the “monogamy relations”that are proposed in [31]. The monogamy relation between two witnesses of contextuality realized on two separate degrees of freedom of any quantum state ρimplies X n i¼1 witr½ρðΠi⊗1ÞþX n i¼1 witr½ρð1⊗¯ ΠiÞ ≤2αðG;  wÞ ð15Þ for any  w, where fΠig,f¯ Πigrealize the respective exclusivity graph G. Such relation holds for a large class of contextuality witnesses, including the well-known oddcycle witnesses [31]. The QKD protocol is secure if the mutual information of Alice-Bob is greater than the mutual information of Alice-Eve [30], i.e., IðA∶BÞ>IðA∶EÞ, which for individual attacks and binary output implies SB>S E, taking SBðSEÞas the value of Sð ˜ G; w;dÞobtained by Bob (Eve). Since Eve also knows the input y, she and Bob are in the same state to guess fðx; yÞ. Because of Theorem 2, when Bob observes that the first two terms in Sð ˜ G; w;dÞ attain their maximal values, then M0jyare rank-one projectors realizing ˜ G. We assume that M0jyfor Eve also realizes ˜ G. Now, even if Eve shares arbitrary quantum correlation with the preparation device of Alice, due to the Eq. (15) monogamy relation, the following holds true: X n y¼1 wypBð0jx¼0;yÞþX n y¼1 wypEð0jx¼0;yÞ≤2αðG;  wÞ: ð16Þ Taking the best possible scenario for Eve in which she also observes Eq. (10), the above relation implies SBþSE≤2Sð ˜ G; w;dÞ c:ð17Þ Therefore, whenever Alice-Bob obtains quantum advantage, that is, SB>S ð ˜ G; w;dÞ c, the protocol is secure against such eavesdropping. Subsequently, the key rate can be obtained by r¼IðA∶BÞ−IðA∶EÞ(see Table I in [37]). In addition to the QKD protocol, these communication tasks can also be used to generate quantum randomness in the prepare-and-measure scenario [53–55]. We have discussed this in Appendix D of [37]. Conclusions.—This Letter shows that all forms of quantum contextuality with sufficiently small dimension provide quantum advantage in distributed computation and in various communication protocols without requiring entanglement. In distributed computation, equality problems are essential for implementing large-scale circuits and data verification [27–29] (see Appendix F of [37]). We show the existence of a variant of the equality problem pertaining to every vertex-weighted graph with certain properties providing an advantage over classical communication. Considering equality problems defined by the graphs of a large class of contextuality witnesses, including all quantum state-independent contextuality witnesses, we show that the communication complexity required to execute such problems in classical theory is larger than that in quantum theory. Moreover, the complexity advantage increases with an increase in the number of inputs, identifying a class of equality problems that can be solved only in quantum communication. As further applications of quantum contextuality driven communication tasks, we show how such tasks can be used for semi-device-independent QKD, as well as for the purpose of randomness generation. As interesting open problems for further work, we point out the possibility of extending the security proof of the QKD protocol to arbitrary individual eavesdropping strategies and finding optimal communication complexity advantages. It would also be interesting to extend the link between quantum contextuality and quantum advantage in communication complexity tasks involving more than two parties, like, quantum fingerprinting [56]. D. S. acknowledges National Post-Doctoral Fellowship (PDF/2020/001682) for support. A. C. is supported by Project Qdisc (Project No. US-15097, Universidad de Sevilla), with FEDER funds, QuantERA grant SECRET, by MINECO (Project No. PCI2019-111885-2), and MICINN (Project No. PID2020–113738GB-I00). A. S. M. acknowledges support from Project No. DST/ICPS/ QuEST/2018/98 of the Department of Science & Technology, Government of India. [1] J. S. Bell, Rev. Mod. Phys. 38, 447 (1966). [2] S. Kochen and E. P. Specker, J. Math. Mech. 17, 59 (1967). [3] A. A. Klyachko, M. A. Can, S. Binicioğlu, and A. S. Shumovsky, Phys. Rev. Lett. 101, 020403 (2008). PHYSICAL REVIEW LETTERS 130, 080802 (2023) 080802-5 [4] A. Cabello, Phys. Rev. Lett. 101, 210401 (2008). [5] A. Cabello, S. Severini, and A. Winter, Phys. Rev. Lett. 112, 040401 (2014). [6] C. Budroni, A. Cabello, M. Kleinmann, J.-Å. Larsson, and O. Gühne, Rev. Mod. Phys. 94, 045007 (2022). [7] A. K. Ekert, Phys. Rev. Lett. 67, 661 (1991). [8] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, Rev. Mod. Phys. 82, 665 (2010). [9] T. S. Cubitt, D. Leung, W. Matthews, and A. Winter, Phys. Rev. Lett. 104, 230503 (2010). [10] M. Kleinmann, O. Gühne, J. R. Portillo, J.-Å. Larsson, and A. Cabello, New J. Phys. 13, 113011 (2011). [11] M. Howard, J. Wallman, V. Veitch, and J. Emerson, Nature (London) 510, 351 (2014). [12] A. Cabello, M. Gu, O. Gühne, and Z.-P. Xu, Phys. Rev. Lett. 120, 130401 (2018). [13] A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, R. Horodecki, P. Joshi, W. Kłobus, and A. Wójcik, Phys. Rev. Lett. 112, 120401 (2014). [14] J. Singh, K. Bharti, and Arvind, Phys. Rev. A 95, 062333 (2017). [15] D. Saha, P. Horodecki, and M. Pawłowski, New J. Phys. 21, 093057 (2019). [16] K. Bharti, M. Ray, A. Varvitsiotis, N. A. Warsi, A. Cabello, and L. C. Kwek, Phys. Rev. Lett. 122, 250403 (2019). [17] D. Saha, R. Santos, and R.Augusiak,Quantum4, 302 (2020). [18] P.-E. Emeriau, M. Howard, and S. Mansfield, PRX Quantum 3, 020307 (2022). [19] There is other notion of contextuality, preparation contextuality [20], which has found application in oblivious multiplexing and state discrimination tasks [21–23]. [20] R. W. Spekkens, Phys. Rev. A 71, 052108 (2005). [21] R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner, and G. J. Pryde, Phys. Rev. Lett. 102, 010401 (2009). [22] S. Ghorai and A. K. Pan, Phys. Rev. A 98, 032110 (2018). [23] D. Schmid and R. W. Spekkens, Phys. Rev. X 8, 011015 (2018). [24] P. Badziag, I. Bengtsson, A. Cabello, and I. Pitowsky, Phys. Rev. Lett. 103, 050401 (2009). [25] S. Yu and C. H. Oh, Phys. Rev. Lett. 108, 030402 (2012). [26] M. Kleinmann, C. Budroni, J.-Å. Larsson, O. Gühne, and A. Cabello, Phys. Rev. Lett. 109, 250402 (2012). [27] E. Kushilevitz and N. Nisan, Communication Complexity (Cambridge University Press, Cambridge, England, 2006). [28] T. Roughgarden, Found. Trends Theor. Comput. Sci. 11, 217 (2016). [29] A. Rao and A. Yehudayoff, Communication Complexity: And Applications (Cambridge University Press, Cambridge, England, 2020). [30] M. Pawłowski and N. Brunner, Phys. Rev. A 84, 010302(R) (2011). [31] R. Ramanathan, A. Soeda, P. Kurzyński, and D. Kaszlikowski, Phys. Rev. Lett. 109, 050404 (2012). [32] P. Kurzyński, A. Cabello, and D. Kaszlikowski, Phys. Rev. Lett. 112, 100401 (2014). [33] D. Saha and R. Ramanathan, Phys. Rev. A 95, 030104(R) (2017). [34] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (Macmillan, London, 1976). [35] A. Cabello, Phys. Rev. A 93, 032102 (2016). [36] A. Cabello, Phys. Rev. Lett. 127, 070401 (2021). [37] See Supplemental Material at http://link.aps.org/ supplemental/10.1103/PhysRevLett.130.080802 for proof of all the theorems, explicit examples of the communication tasks based on well-known contextuality witnesses, robustness analysis of the quantum advantage, and details of QKD and randomness protocol. [38] R. de Wolf, Theor. Comput. Sci. 287, 337 (2002). [39] H. Buhrman, R. Cleve, and A. Wigderson, in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, New York, 1998), p. 63. [40] Chromatic number is the smallest number of colors needed to color the vertices of Gso that no two adjacent vertices share the same color [34]. [41] A. Cabello, arXiv:1112.5149. [42] R. Ramanathan and P. Horodecki, Phys. Rev. Lett. 112, 040404 (2014). [43] A. Cabello, M. Kleinmann, and C. Budroni, Phys. Rev. Lett. 114, 250402 (2015). [44] U. Feige, Combinatorica 17, 79 (1997). [45] U. Feige, in Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing (ACM, New York, 1995), p. 635. [46] Note that dmin is lower bounded by the size of the maximum clique, i.e., the clique of largest size, of G. [47] A. Peres, J. Phys. A 24, L175 (1991). [48] A. Cabello, J. Estebaranz, and G. García-Alcaine, Phys. Lett. A 212, 183 (1996). [49] Z.-P. Xu, J. Steinberg, J. Singh, A. J. López-Tarrida, J. R. Portillo, and A. Cabello, Graph-theoretic approach to Bell experiments with low detection efficiency, arXiv:2205 .05098. [50] M. W. Newman, Independent Sets and Eigenspaces, Ph.D. thesis (University of Waterloo, 2004). [51] P. Frankl and V. Rodl, Trans. Am. Math. Soc. 300, 259 (1987). [52] C. H. Bennett and G. Brassard, Theor. Comput. Sci. 560,7 (2014). [53] H.-W. Li, M. Pawłowski, Z.-Q. Yin, G.-C. Guo, and Z.-F. Han, Phys. Rev. A 85, 052308 (2012). [54] T. Lunghi, J. B. Brask, C. C. W. Lim, Q. Lavigne, J. Bowles, A. Martin, H. Zbinden, and N. Brunner, Phys. Rev. Lett. 114, 150501 (2015). [55] Y.-G. Han, Z.-Q. Yin, H.-W. Li, W. Chen, S. Wang, G.-C. Guo, and Z.-F. Han, Phys. Rev. A 93, 032332 (2016). [56] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Phys. Rev. Lett. 87, 167902 (2001). PHYSICAL REVIEW LETTERS 130, 080802 (2023) 080802-6