# Gadget structures in proofs of the Kochen-Specker theorem

Ravishankar Ramanathan1, Monika Rosicka2, Karol Horodecki3,4, Stefano Pironio5, Michał Horodecki2,6, and Paweł Horodecki6,7

1Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong
2Institute of Theoretical Physics and Astrophysics and the National Quantum Information Centre, Faculty of Mathematics, Physics and Informatics, University of Gdansk, 80-308 Gdansk, Poland.
3Institute of Informatics Faculty of Mathematics, Physics and Informatics, University of Gdansk, 80-308 Gdansk, Poland
4International Centre for Theory of Quantum Technologies, University of Gdansk, Wita Stwosza 63, 80-308 Gdansk, Poland
5Laboratoire d'Information Quantique, Université Libre de Bruxelles, Belgium
6International Centre for Theory of Quantum Technologies, University of Gdańsk, Wita Stwosza 63, 80-308 Gdańsk, Poland
7Faculty of Applied Physics and Mathematics, National Quantum Information Centre, Gdańsk University of Technology, Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland

### Abstract

The Kochen-Specker theorem is a fundamental result in quantum foundations that has spawned massive interest since its inception. We show that within every Kochen-Specker graph, there exist interesting subgraphs which we term $01$-gadgets, that capture the essential contradiction necessary to prove the Kochen-Specker theorem, i.e,. every Kochen-Specker graph contains a $01$-gadget and from every $01$-gadget one can construct a proof of the Kochen-Specker theorem. Moreover, we show that the $01$-gadgets form a fundamental primitive that can be used to formulate state-independent and state-dependent statistical Kochen-Specker arguments as well as to give simple constructive proofs of an extended'' Kochen-Specker theorem first considered by Pitowsky in [22].

### ► References

[1] S. Kochen and E.P. Specker. The Problem of Hidden Variables in Quantum Mechanics. Journal of Mathematics and Mechanics Vol. 17, No. 1, 59 (1967).
https:/​/​www.jstor.org/​stable/​24902153

[2] A. A. Abbott, C. S. Calude and K. Svozil. A variant of the Kochen-Specker theorem localising value indefiniteness. Journal of Mathematical Physics 56, 102201 (2015).
https:/​/​doi.org/​10.1063/​1.4931658

[3] A. A. Abbott, C. S. Calude, J. Conder and K. Svozil. Strong Kochen-Specker theorem and incomputability of quantum randomness. Phys. Rev. A 86(6), 062109 (2012).
https:/​/​doi.org/​10.1103/​PhysRevA.86.062109

[4] A. A. Klyachko, M. A. Can, S. Binicoglu and A. S. Shumovsky. Simple Test for Hidden Variables in Spin-1 Systems. Phys. Rev. Lett. 101, 020403 (2008).
https:/​/​doi.org/​10.1103/​PhysRevLett.101.020403

[5] C. D. Godsil and M. W. Newman. Coloring an orthogonality graph. SIAM J. Discrete Math., 22(2): 683 (2008).
https:/​/​doi.org/​10.1137/​050639715

[6] A. Cabello, S. Severini and A. Winter. Graph-Theoretic Approach to Quantum Correlations. Phys. Rev. Lett. 112, 040401 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.112.040401

[7] A. Cabello, S. Severini and A. Winter. (Non-)Contextuality of Physical Theories as an Axiom Mittag-Leffler-2010fall Report No. 8 (2010). https:/​/​arxiv.org/​abs/​1010.2163.
arXiv:1010.2163
http:/​/​www.mittag-leffler.se/​sites/​default/​files/​IML-1011f-08.pdf

[8] A. A. Abbott, C. S. Calude and K. Svozil. A quantum random number generator certified by value indefiniteness. Mathematical Structures in Computer Science Vol. 24, Issue 3 (Developments of the Concepts of Randomness, Statistic and Probability), e240303 (2014).
https:/​/​doi.org/​10.1017/​S0960129512000692

[9] A. A. Abbott, C. S. Calude and K. Svozil. Value-indefinite observables are almost everywhere. Phys. Rev. A 89, 032109 (2014).
https:/​/​doi.org/​10.1103/​PhysRevA.89.032109

[10] R. Ramanathan, F. G. S. L. Brandao, K. Horodecki, M. Horodecki, P. Horodecki and H. Wojewodka. Randomness Amplification under Minimal Fundamental Assumptions on the Devices. Phys. Rev. Lett. 117, 230501 (2016).
https:/​/​doi.org/​10.1103/​PhysRevLett.117.230501

[11] F.G.S.L. Brandão, R. Ramanathan, A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, T. Szarek, and H. Wojewódka. Robust Device-Independent Randomness Amplification with Few Devices. Nat. Comm. 7, 11345 (2016).
https:/​/​doi.org/​10.1038/​ncomms11345

[12] H. Wojewódka, F. G. S. L. Brandão, A. Grudka, M. Horodecki, K. Horodecki, P. Horodecki, M. Pawĺowski, R. Ramanathan. Amplifying the Randomness of Weak Sources Correlated with Devices. IEEE Trans. on Inf. Theory. Vol. 63, No. 11, pp. 7592-7611 (2017).
https:/​/​doi.org/​10.1109/​TIT.2017.2738010

[13] A. Cabello, L. E. Danielsen, A. J. Lopez-Tarrida, J. R. Portillo. Basic exclusivity graphs in quantum correlations. Phys. Rev. A 88, 032104 (2013).
https:/​/​doi.org/​10.1103/​PhysRevA.88.032104

[14] A. Cabello. State-independent quantum contextuality and maximum nonlocality. arXiv:1112.5149 (2011).
arXiv:1112.5149

[15] F. Arends. A lower bound on the size of the smallest Kochen-Specker vector system. Master’s thesis, Oxford University (2009).

[16] F. Arends, J. Ouaknine, and C. W. Wampler. On Searching for Small Kochen-Specker Vector Systems. In: Kolman P., Kratochvíl J. (eds) Graph-Theoretic Concepts in Computer Science. WG 2011. Lecture Notes in Computer Science, vol 6986. Springer, Berlin, Heidelberg (2011).
https:/​/​doi.org/​10.1007/​978-3-642-25870-1_4

[17] R. K. Clifton. Getting Contextual and Nonlocal Elements-of-Reality the Easy Way. American Journal of Physics, 61: 443 (1993).
https:/​/​doi.org/​10.1119/​1.17239

[18] A. Cabello, J. Estebaranz and G. García-Alcaine. Bell-Kochen-Specker Theorem: A Proof with 18 vectors. Phys. Lett. A Vol. 212, Issue 4, 183 (1996).
https:/​/​doi.org/​10.1016/​0375-9601(96)00134-X

[19] C. Held. The Kochen-Specker Theorem. The Stanford Encyclopedia of Philosophy (Fall 2016 Edition), Edward N. Zalta (ed.), (2016).
https:/​/​plato.stanford.edu/​entries/​kochen-specker/​

[20] A. Cabello. Experimentally Testable State-Independent Quantum Contextuality. Phys. Rev. Lett. 101, 210401 (2008).
https:/​/​doi.org/​10.1103/​PhysRevLett.101.210401

[21] A. Cabello and G. García-Alcaine. Bell-Kochen-Specker Theorem for any finite dimension $n \geq 3$. J. Phys A: Math. and Gen., 29, 1025, (1996).
https:/​/​doi.org/​10.1088/​0305-4470/​29/​5/​016

[22] I. Pitowsky. Infinite and finite Gleason's theorems and the logic of indeterminacy. Journal of Mathematical Physics 39, 218 (1998).
https:/​/​doi.org/​10.1063/​1.532334

[23] E. Hrushovski and I. 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 Vol. 35, Issue 2, 177-194 (2004).
https:/​/​doi.org/​10.1016/​j.shpsb.2003.10.002

[24] A. M. Gleason. Measures on the Closed Subspaces of a Hilbert Space. Journal of Mathematics and Mechanics Vol. 6, No. 6, 885 (1957).
https:/​/​www.jstor.org/​stable/​24900629

[25] S. Yu and C. H. Oh. State-Independent Proof of Kochen-Specker Theorem with 13 Rays. Phys. Rev. Lett. 108, 030402 (2012).
https:/​/​doi.org/​10.1103/​PhysRevLett.108.030402

[26] A. Stairs. Quantum Logic, Realism, and Value Definiteness. Philos. Sci. 50, 4, 578 (1983).
https:/​/​www.jstor.org/​stable/​187557

[27] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press (2001).
https:/​/​mitpress.mit.edu/​books/​introduction-algorithms-second-edition

[28] L. Lovasz, M. Saks, A. Schrijver. Orthogonal representation and connectivity of graphs. Linear Algebra and its applications, 4, 114-115, 439 (1987).
https:/​/​doi.org/​10.1016/​0024-3795(89)90475-8

[29] R. Ramanathan, M. Horodecki, S. Pironio, K. Horodecki, and P. Horodecki. Generic randomness amplification schemes using Hardy paradoxes. arXiv: 1810.11648 (2018).
arXiv:1810.11648

[30] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas. The strong perfect graph theorem. Annals of Mathematics, 164 (1): 51 (2006).
https:/​/​doi.org/​10.4007/​annals.2006.164.51

[31] R. Peeters. Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica 16, 3, 417 (1996).
https:/​/​doi.org/​10.1007/​BF01261326

[32] A Cabello and G Garcia-Alcaine. A hidden-variables versus quantum mechanics experiment. Journal of Phys. A: Math. and General, 28, No. 13 (1995).
https:/​/​doi.org/​10.1088/​0305-4470/​28/​13/​016

[33] P. Badzia̧g, I. Bengtsson, A. Cabello, and I. Pitowsky. Universality of State-Independent Violation of Correlation Inequalities for Noncontextual Theories. Phys. Rev. Lett. 103, 050401 (2009).
https:/​/​doi.org/​10.1103/​PhysRevLett.103.050401

[34] A. Cabello, J. R. Portillo, A. Solís, and K. Svozil. Minimal true-implies-false and true-implies-true sets of propositions in noncontextual hidden-variable theories. Phys. Rev. A 98, 012106 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.012106

### Cited by

[1] Karl Svozil, "Extensions of Hardy-type true-implies-false gadgets to classically obtain indistinguishability", Physical Review A 103 2, 022204 (2021).

[2] Václav Voráček and Mirko Navara, "Generalised Kochen–Specker Theorem in Three Dimensions", Foundations of Physics 51 3, 67 (2021).

[3] Karl Svozil, "What Is so Special about Quantum Clicks?", Entropy 22 6, 602 (2020).

[4] Karl Svozil, "Classical predictions for intertwined quantum observables are contingent and thus inconclusive", arXiv:1808.00813.

[5] Ravishankar Ramanathan, Michał Horodecki, Hammad Anwer, Stefano Pironio, Karol Horodecki, Marcus Grünfeld, Sadiq Muhammad, Mohamed Bourennane, and Paweł Horodecki, "Practical No-Signalling proof Randomness Amplification using Hardy paradoxes and its experimental implementation", arXiv:1810.11648.

[6] Mohammad H. Shekarriz and Karl Svozil, "Noncontextual coloring of orthogonality hypergraphs", arXiv:2105.08520.

The above citations are from Crossref's cited-by service (last updated successfully 2021-08-01 15:05:50) and SAO/NASA ADS (last updated successfully 2021-08-01 15:05:51). The list may be incomplete as not all publishers provide suitable and complete citation data.