# Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem

Victoria J Wright1 and Ravi Kunjwal2

1ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels, Spain
2Centre for Quantum Information and Communication, Ecole polytechnique de Bruxelles, CP 165, Université libre de Bruxelles, 1050 Brussels, Belgium

### Abstract

The Kochen–Specker (KS) theorem reveals the nonclassicality of single quantum systems. In contrast, Bell's theorem and entanglement concern the nonclassicality of composite quantum systems. Accordingly, unlike incompatibility, entanglement and Bell non-locality are not necessary to demonstrate KS-contextuality. However, here we find that for multiqubit systems, entanglement and non-locality are both essential to proofs of the Kochen–Specker theorem. Firstly, we show that unentangled measurements (a strict superset of local measurements) can never yield a logical (state-independent) proof of the KS theorem for multiqubit systems. In particular, unentangled but nonlocal measurements—whose eigenstates exhibit ''nonlocality without entanglement"—are insufficient for such proofs. This also implies that proving Gleason's theorem on a multiqubit system necessarily requires entangled projections, as shown by Wallach [Contemp Math, 305: 291-298 (2002)]. Secondly, we show that a multiqubit state admits a statistical (state-dependent) proof of the KS theorem if and only if it can violate a Bell inequality with projective measurements. We also establish the relationship between entanglement and the theorems of Kochen–Specker and Gleason more generally in multiqudit systems by constructing new examples of KS sets. Finally, we discuss how our results shed new light on the role of multiqubit contextuality as a resource within the paradigm of quantum computation with state injection.

Very small physical systems, such as photons of light, behave in ways that contradict the theories of physics scientists used before the advent of quantum theory. Quantum theory was developed to describe these very small systems and does so very successfully. Broadly, the theories predating quantum theory, often called classical theories, are all noncontextual. A theory is noncontextual if every observable property of a system, such as its position, can be assumed to have a definite value at all times such that whenever and however this property is measured one will find this value. The Kochen-Specker theorem demonstrates how the predictions of quantum theory cannot be explained in a noncontextual way.

Quantum theory also has other major differences from classical theories, with two prominent examples being Bell nonlocality and entanglement. Unlike Kochen-Specker contextuality described above which involves a single quantum system, Bell nonlocality and entanglement are properties only present when we study multiple quantum systems together. In this work, however, we show that for systems of multiple qubits (as in a quantum computer) both Bell nonlocality and entanglement are essential for the presence of Kochen–Specker contextuality.

As well as relevance to the foundations of physics, we discuss how our findings may lead to a better understanding of quantum advantage in quantum computing. Quantum advantage must stem from the differences between the quantum and classical physics that describes quantum and classical computers, respectively. Therefore, understanding the nonclassicality of the multiqubit systems we study presents a path a harnessing the power of quantum advantage.

### ► References

[1] Erwin Schrödinger. Discussion of probability relations between separated systems. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 31, pages 555–563. Cambridge University Press, 1935. doi:10.1017/​S0305004100013554.
https:/​/​doi.org/​10.1017/​S0305004100013554

[2] Noah Linden and Sandu Popescu. Good dynamics versus bad kinematics: Is entanglement needed for quantum computation? Phys. Rev. Lett., 87:047901, 2001. doi:10.1103/​PhysRevLett.87.047901.
https:/​/​doi.org/​10.1103/​PhysRevLett.87.047901

[3] Animesh Datta and Guifre Vidal. Role of entanglement and correlations in mixed-state quantum computation. Phys. Rev. A, 75:042310, 2007. doi:10.1103/​PhysRevA.75.042310.
https:/​/​doi.org/​10.1103/​PhysRevA.75.042310

[4] Victor Veitch, Christopher Ferrie, David Gross, and Joseph Emerson. Negative quasi-probability as a resource for quantum computation. New J. Phys., 14(11):113011, 2012. doi:10.1088/​1367-2630/​14/​11/​113011.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​113011

[5] Mark Howard, Joel Wallman, Victor Veitch, and Joseph Emerson. Contextuality supplies the `magic' for quantum computation. Nature, 510(7505):351–355, 2014. doi:10.1038/​nature13460.
https:/​/​doi.org/​10.1038/​nature13460

[6] Claudio Carmeli, Teiko Heinosaari, and Alessandro Toigo. Quantum random access codes and incompatibility of measurements. EPL (Europhysics Letters), 130(5):50001, 2020. doi:10.1209/​0295-5075/​130/​50001.
https:/​/​doi.org/​10.1209/​0295-5075/​130/​50001

[7] Toby S Cubitt, Debbie Leung, William Matthews, and Andreas Winter. Improving zero-error classical communication with entanglement. Phys. Rev. Lett., 104:230503, 2010. doi:10.1103/​PhysRevLett.104.230503.
https:/​/​doi.org/​10.1103/​PhysRevLett.104.230503

[8] Shiv Akshar Yadavalli and Ravi Kunjwal. Contextuality in entanglement-assisted one-shot classical communication. arXiv:2006.00469, 2020. doi:10.48550/​arXiv.2006.00469.
https:/​/​doi.org/​10.48550/​arXiv.2006.00469
arXiv:2006.00469

[9] Máté Farkas, Maria Balanzó-Juandó, Karol Łukanowski, Jan Kołodyński, and Antonio Acín. Bell nonlocality is not sufficient for the security of standard device-independent quantum key distribution protocols. Phys. Rev. Lett., 127:050503, 2021. doi:10.1103/​PhysRevLett.127.050503.
https:/​/​doi.org/​10.1103/​PhysRevLett.127.050503

[10] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2:79, 2018. doi:10.22331/​q-2018-08-06-79.
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[11] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019. doi:10.1038/​s41586-019-1666-5.
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[12] Simon Kochen and Ernst P Specker. The problem of hidden variables in quantum mechanics. J. Math. Mech., 17(1):59–87, 1967. doi:10.1512/​iumj.1968.17.17004.
https:/​/​doi.org/​10.1512/​iumj.1968.17.17004

[13] Juan Bermejo-Vega, Nicolas Delfosse, Dan E Browne, Cihan Okay, and Robert Raussendorf. Contextuality as a resource for models of quantum computation with qubits. Phys. Rev. Lett., 119:120505, 2017. doi:10.1103/​PhysRevLett.119.120505.
https:/​/​doi.org/​10.1103/​PhysRevLett.119.120505

[14] John Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1(RX-1376):195–200, 1964. doi:10.1103/​PhysicsPhysiqueFizika.1.195.
https:/​/​doi.org/​10.1103/​PhysicsPhysiqueFizika.1.195

[15] John S Bell. On the Problem of Hidden Variables in Quantum Mechanics. Rev. Mod. Phys., 38:447–452, 1966. doi:10.1103/​RevModPhys.38.447.
https:/​/​doi.org/​10.1103/​RevModPhys.38.447

[16] Andrew M Gleason. Measures on the closed subspaces of a Hilbert space. Indiana Univ. Math. J, 6:885, 1957. doi:10.1512/​iumj.1957.6.56050.
https:/​/​doi.org/​10.1512/​iumj.1957.6.56050

[17] Robert W Spekkens. Quasi-Quantization: Classical Statistical Theories with an Epistemic Restriction, pages 83–135. Springer Netherlands, Dordrecht, 2016. doi:10.1007/​978-94-017-7303-4_4.
https:/​/​doi.org/​10.1007/​978-94-017-7303-4_4

[18] Ravi Kunjwal and Robert W Spekkens. From the Kochen-Specker theorem to noncontextuality inequalities without assuming determinism. Phys. Rev. Lett., 115:110403, 2015. doi:10.1103/​PhysRevLett.115.110403.
https:/​/​doi.org/​10.1103/​PhysRevLett.115.110403

[19] Ravi Kunjwal and Robert W Spekkens. From statistical proofs of the Kochen-Specker theorem to noise-robust noncontextuality inequalities. Phys. Rev. A, 97:052110, 2018. doi:10.1103/​PhysRevA.97.052110.
https:/​/​doi.org/​10.1103/​PhysRevA.97.052110

[20] Alexander A Klyachko, M Ali Can, Sinem Binicioğlu, and Alexander S Shumovsky. Simple Test for Hidden Variables in Spin-1 Systems. Phys. Rev. Lett., 101:020403, 2008. doi:10.1103/​PhysRevLett.101.020403.
https:/​/​doi.org/​10.1103/​PhysRevLett.101.020403

[21] Robert W Spekkens. Contextuality for preparations, transformations, and unsharp measurements. Phys. Rev. A, 71:052108, 2005. doi:10.1103/​PhysRevA.71.052108.
https:/​/​doi.org/​10.1103/​PhysRevA.71.052108

[22] Ravi Kunjwal and Sibasish Ghosh. Minimal state-dependent proof of measurement contextuality for a qubit. Phys. Rev. A, 89:042118, 2014. doi:10.1103/​PhysRevA.89.042118.
https:/​/​doi.org/​10.1103/​PhysRevA.89.042118

[23] Ravi Kunjwal. Contextuality beyond the Kochen–Specker theorem. arXiv:1612.07250, 2016. doi:10.48550/​arXiv.1612.07250.
https:/​/​doi.org/​10.48550/​arXiv.1612.07250
arXiv:1612.07250

[24] Paul Busch. Quantum states and generalized observables: a simple proof of Gleason's theorem. Phys. Rev. Lett., 91:120403, 2003. doi:10.1103/​physrevlett.91.120403.
https:/​/​doi.org/​10.1103/​physrevlett.91.120403

[25] Carlton M Caves, Christopher A Fuchs, Kiran K Manne, and Joseph M Renes. Gleason-type derivations of the quantum probability rule for generalized measurements. Found. Phys., 34:193–209, 2004. doi:10.1023/​b:foop.0000019581.00318.a5.
https:/​/​doi.org/​10.1023/​b:foop.0000019581.00318.a5

[26] Victoria J Wright and Stefan Weigert. A Gleason-type theorem for qubits based on mixtures of projective measurements. J. Phys. A, 52:055301, 2019. doi:10.1088/​1751-8121/​aaf93d.
https:/​/​doi.org/​10.1088/​1751-8121/​aaf93d

[27] Nolan R Wallach. An unentangled Gleason's theorem. Contemp Math, 305:291–298, 2002. doi:10.1090/​conm/​305/​05226.
https:/​/​doi.org/​10.1090/​conm/​305/​05226

[28] Charles H Bennett, David P DiVincenzo, Christopher A Fuchs, Tal Mor, Eric Rains, Peter W Shor, John A Smolin, and William K Wootters. Quantum nonlocality without entanglement. Phys. Rev. A, 59:1070–1091, 1999. doi:10.1103/​PhysRevA.59.1070.
https:/​/​doi.org/​10.1103/​PhysRevA.59.1070

[29] David N Mermin. Hidden variables and the two theorems of John Bell. Rev. Mod. Phys., 65:803–815, 1993. doi:10.1103/​RevModPhys.65.803.
https:/​/​doi.org/​10.1103/​RevModPhys.65.803

[30] Asher Peres. Two simple proofs of the Kochen–Specker theorem. J. Phys. A, 24(4):L175, 1991. doi:10.1088/​0305-4470/​24/​4/​003.
https:/​/​doi.org/​10.1088/​0305-4470/​24/​4/​003

[31] Asher Peres. Incompatible results of quantum measurements. Phys. Lett. A, 151(3-4):107–108, 1990. doi:10.1016/​0375-9601(90)90172-K.
https:/​/​doi.org/​10.1016/​0375-9601(90)90172-K

[32] Antonio Acín, Tobias Fritz, Anthony Leverrier, and Ana Belén Sainz. A combinatorial approach to nonlocality and contextuality. Commun. Math. Phys., 334(2):533–628, 2015. doi:10.1007/​s00220-014-2260-1.
https:/​/​doi.org/​10.1007/​s00220-014-2260-1

[33] Ravi Kunjwal. Beyond the Cabello-Severini-Winter framework: Making sense of contextuality without sharpness of measurements. Quantum, 3:184, 2019. doi:10.22331/​q-2019-09-09-184.
https:/​/​doi.org/​10.22331/​q-2019-09-09-184

[34] Ravi Kunjwal. Hypergraph framework for irreducible noncontextuality inequalities from logical proofs of the Kochen-Specker theorem. Quantum, 4:219, 2020. doi:10.22331/​q-2020-01-10-219.
https:/​/​doi.org/​10.22331/​q-2020-01-10-219

[35] Ehud Hrushovski and Itamar Pitowsky. Generalizations of Kochen and Specker's theorem and the effectiveness of Gleason's theorem. Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics, 35(2):177–194, 2004. doi:10.1016/​j.shpsb.2003.10.002.
https:/​/​doi.org/​10.1016/​j.shpsb.2003.10.002

[36] Lin Chen and Dragomir Z Djokovic. Orthogonal product bases of four qubits. J. Phys. A, 50(39):395301, 2017. doi:10.1088/​1751-8121/​aa8546.
https:/​/​doi.org/​10.1088/​1751-8121/​aa8546

[37] Matthew S Leifer. Is the quantum state real? An extended review of $\psi$-ontology theorems. Quanta, 3(1):67–155, 2014. doi:10.12743/​quanta.v3i1.22.
https:/​/​doi.org/​10.12743/​quanta.v3i1.22

[38] Matthew S Leifer and Owen J E Maroney. Maximally epistemic interpretations of the quantum state and contextuality. Phys. Rev. Lett., 110:120401, 2013. doi:10.1103/​PhysRevLett.110.120401.
https:/​/​doi.org/​10.1103/​PhysRevLett.110.120401

[39] Ravi Kunjwal. Fine's theorem, noncontextuality, and correlations in Specker's scenario. Phys. Rev. A, 91:022108, 2015. doi:10.1103/​PhysRevA.91.022108.
https:/​/​doi.org/​10.1103/​PhysRevA.91.022108

[40] Tomáš Gonda, Ravi Kunjwal, David Schmid, Elie Wolfe, and Ana Belén Sainz. Almost quantum correlations are inconsistent with Specker's principle. 2:87. doi:10.22331/​q-2018-08-27-87.
https:/​/​doi.org/​10.22331/​q-2018-08-27-87

[41] Arthur Fine. Hidden variables, joint probability, and the Bell inequalities. Phys. Rev. Lett., 48:291–295, 1982. doi:10.1103/​physrevlett.48.291.
https:/​/​doi.org/​10.1103/​physrevlett.48.291

[42] Arthur Fine. Joint distributions, quantum correlations, and commuting observables. J. Math. Phys., 23(7):1306–1310, 1982. doi:10.1063/​1.525514.
https:/​/​doi.org/​10.1063/​1.525514

[43] Samson Abramsky and Adam Brandenburger. The sheaf-theoretic structure of non-locality and contextuality. New J. Phys., 13(11):113036, 2011. doi:10.1088/​1367-2630/​13/​11/​113036.
https:/​/​doi.org/​10.1088/​1367-2630/​13/​11/​113036

[44] Rafael Chaves and Tobias Fritz. Entropic approach to local realism and noncontextuality. Phys. Rev. A, 85:032113, 2012. doi:10.1103/​PhysRevA.85.032113.
https:/​/​doi.org/​10.1103/​PhysRevA.85.032113

[45] Remigiusz Augusiak, Tobias Fritz, Ma Kotowski, Mi Kotowski, Marcin Pawłowski, Maciej Lewenstein, and Antonio Acín. Tight Bell inequalities with no quantum violation from qubit unextendible product bases. Phys. Rev. A, 85(4):042113, 2012. doi:10.1103/​physreva.85.042113.
https:/​/​doi.org/​10.1103/​physreva.85.042113

[46] Victoria J Wright and Ravi Kunjwal. Embedding Peres. GitHub repository, 2021. URL: https:/​/​github.com/​vickyjwright/​embeddingperes.
https:/​/​github.com/​vickyjwright/​embeddingperes

[47] Daniel McNulty, Bogdan Pammer, and Stefan Weigert. Mutually unbiased product bases for multiple qudits. J. Math. Phys., 57(3):032202, 2016. doi:10.1063/​1.4943301.
https:/​/​doi.org/​10.1063/​1.4943301

[48] David Schmid, Haoxing Du, John H Selby, and Matthew F Pusey. The only noncontextual model of the stabilizer subtheory is Gross's. Phys. Rev. Lett., 129:120403, 2021 doi:10.1103/​PhysRevLett.129.120403.
https:/​/​doi.org/​10.1103/​PhysRevLett.129.120403

[49] Daniel Gottesman. The Heisenberg representation of quantum computers. In Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics, pages 32–43. Cambridge, MA, International Press, 1998. doi:10.48550/​arXiv.quant-ph/​9807006.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​9807006
arXiv:quant-ph/9807006

[50] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A, 70:052328, 2004. doi:10.1103/​PhysRevA.70.052328.
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[51] Adán Cabello, Simone Severini, and Andreas Winter. Graph-theoretic approach to quantum correlations. Phys. Rev. Lett., 112:040401, 2014. doi:10.1103/​PhysRevLett.112.040401.
https:/​/​doi.org/​10.1103/​PhysRevLett.112.040401

[52] Reinhard F Werner. Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model. Phys. Rev. A, 40:4277–4281, 1989. doi:10.1103/​PhysRevA.40.4277.
https:/​/​doi.org/​10.1103/​PhysRevA.40.4277

[53] Michael Redhead. Incompleteness, nonlocality and realism: A prolegomenon to the philosophy of quantum mechanics. Oxford University Press, 1987.

[54] Tobias Fritz, Ana Belén Sainz, Remigiusz Augusiak, J Bohr Brask, Rafael Chaves, Anthony Leverrier, and Antonio Acín. Local orthogonality as a multipartite principle for quantum correlations. Nature communications, 4(1):1–7, 2013. doi:10.1038/​ncomms3263.
https:/​/​doi.org/​10.1038/​ncomms3263

[55] Julien Degorre, Marc Kaplan, Sophie Laplante, and Jérémie Roland. The communication complexity of non-signaling distributions. In Mathematical Foundations of Computer Science 2009, pages 270–281, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. doi:10.1007/​978-3-642-03816-7_24.
https:/​/​doi.org/​10.1007/​978-3-642-03816-7_24

### Cited by

[1] Ravi Kunjwal and Ämin Baumeler, "Trading causal order for locality", arXiv:2202.00440, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2023-02-07 14:51:32). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-02-07 14:51:31).