Gadget structures in proofs of the Kochen-Specker theorem

Ravishankar Ramanathan; Monika Rosicka; Karol Horodecki; Stefano Pironio; Michał Horodecki; Paweł Horodecki

doi:10.22331/q-2020-08-14-308

Gadget structures in proofs of the Kochen-Specker theorem

Ravishankar Ramanathan¹, Monika Rosicka², Karol Horodecki^3,4, Stefano Pironio⁵, Michał Horodecki^2,6, and Paweł Horodecki^6,7

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

Published:	2020-08-14, volume 4, page 308
Eprint:	arXiv:1807.00113v2
Doi:	https://doi.org/10.22331/q-2020-08-14-308
Citation:	Quantum 4, 308 (2020).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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].

► BibTeX data

@article{Ramanathan2020gadgetstructuresin,
  doi = {10.22331/q-2020-08-14-308},
  url = {https://doi.org/10.22331/q-2020-08-14-308},
  title = {Gadget structures in proofs of the {K}ochen-{S}pecker theorem},
  author = {Ramanathan, Ravishankar and Rosicka, Monika and Horodecki, Karol and Pironio, Stefano and Horodecki, Micha{\l{}} and Horodecki, Pawe{\l{}}},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {308},
  month = aug,
  year = {2020}
}

► 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).
http://www.cs.ox.ac.uk/people/joel.ouaknine/download/arends09.pdf

[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] Yuan Liu, Ravishankar Ramanathan, Karol Horodecki, Monika Rosicka, and Paweł Horodecki, "Optimal measurement structures for contextuality applications", npj Quantum Information 9 1, 63 (2023).

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

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

[4] Ravishankar Ramanathan, Yuan Liu, and Paweł Horodecki, "Large violations in Kochen Specker contextuality and their applications", New Journal of Physics 24 3, 033035 (2022).

[5] Adán Cabello, "Converting Contextuality into Nonlocality", Physical Review Letters 127 7, 070401 (2021).

[6] Mohammad H. Shekarriz and Karl Svozil, "Noncontextual coloring of orthogonality hypergraphs", Journal of Mathematical Physics 63 3, 032104 (2022).

[7] Mordecai Waegell and P. K. Aravind, "Golay codes and quantum contextuality", Physical Review A 106 6, 062421 (2022).

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

[9] 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, (2018).

[10] Karl Svozil, "Varieties of contextuality based on probability and structural nonembeddability", arXiv:2103.06110, (2021).

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-30 22:21:38) and SAO/NASA ADS (last updated successfully 2023-09-30 22:21:39). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.