{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T13:34:08Z","timestamp":1776778448279,"version":"3.51.2"},"reference-count":34,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>01<\/mml:mn><\/mml:math>-gadgets, that capture the essential contradiction necessary to prove the Kochen-Specker theorem, i.e,. every Kochen-Specker graph contains a <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>01<\/mml:mn><\/mml:math>-gadget and from every <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>01<\/mml:mn><\/mml:math>-gadget one can construct a proof of the Kochen-Specker theorem. Moreover, we show that the <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>01<\/mml:mn><\/mml:math>-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 \\cite{Pitowsky}.<\/jats:p>","DOI":"10.22331\/q-2020-08-14-308","type":"journal-article","created":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T15:11:54Z","timestamp":1597417914000},"page":"308","source":"Crossref","is-referenced-by-count":14,"title":["Gadget structures in proofs of the Kochen-Specker theorem"],"prefix":"10.22331","volume":"4","author":[{"given":"Ravishankar","family":"Ramanathan","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monika","family":"Rosicka","sequence":"additional","affiliation":[{"name":"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."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karol","family":"Horodecki","sequence":"additional","affiliation":[{"name":"Institute of Informatics Faculty of Mathematics, Physics and Informatics, University of Gdansk, 80-308 Gdansk, Poland"},{"name":"International Centre for Theory of Quantum Technologies, University of Gdansk, Wita Stwosza 63, 80-308 Gdansk, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Pironio","sequence":"additional","affiliation":[{"name":"Laboratoire d'Information Quantique, Universit\u00e9 Libre de Bruxelles, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Horodecki","sequence":"additional","affiliation":[{"name":"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."},{"name":"International Centre for Theory of Quantum Technologies, University of Gda\u0144sk, Wita Stwosza 63, 80-308 Gda\u0144sk, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Horodecki","sequence":"additional","affiliation":[{"name":"International Centre for Theory of Quantum Technologies, University of Gda\u0144sk, Wita Stwosza 63, 80-308 Gda\u0144sk, Poland"},{"name":"Faculty of Applied Physics and Mathematics, National Quantum Information Centre, Gda\u0144sk University of Technology, Gabriela Narutowicza 11\/12, 80-233 Gda\u0144sk, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2020,8,14]]},"reference":[{"key":"0","unstructured":"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)."},{"key":"1","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1063\/1.4931658"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.86.062109"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.101.020403"},{"key":"4","doi-asserted-by":"publisher","unstructured":"C. D. Godsil and M. W. Newman. Coloring an orthogonality graph. SIAM J. Discrete Math., 22(2): 683 (2008).","DOI":"10.1137\/050639715"},{"key":"5","doi-asserted-by":"publisher","unstructured":"A. Cabello, S. Severini and A. Winter. Graph-Theoretic Approach to Quantum Correlations. Phys. Rev. Lett. 112, 040401 (2014).","DOI":"10.1103\/PhysRevLett.112.040401"},{"key":"6","unstructured":"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."},{"key":"7","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1017\/S0960129512000692"},{"key":"8","doi-asserted-by":"publisher","unstructured":"A. A. Abbott, C. S. Calude and K. Svozil. Value-indefinite observables are almost everywhere. Phys. Rev. A 89, 032109 (2014).","DOI":"10.1103\/PhysRevA.89.032109"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.117.230501"},{"key":"10","doi-asserted-by":"publisher","unstructured":"F.G.S.L. Brand\u00e3o, R. Ramanathan, A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, T. Szarek, and H. Wojew\u00f3dka. Robust Device-Independent Randomness Amplification with Few Devices. Nat. Comm. 7, 11345 (2016).","DOI":"10.1038\/ncomms11345"},{"key":"11","doi-asserted-by":"publisher","unstructured":"H. Wojew\u00f3dka, F. G. S. L. Brand\u00e3o, A. Grudka, M. Horodecki, K. Horodecki, P. Horodecki, M. Paw\u013aowski, R. Ramanathan. Amplifying the Randomness of Weak Sources Correlated with Devices. IEEE Trans. on Inf. Theory. Vol. 63, No. 11, pp. 7592-7611 (2017).","DOI":"10.1109\/TIT.2017.2738010"},{"key":"12","doi-asserted-by":"publisher","unstructured":"A. Cabello, L. E. Danielsen, A. J. Lopez-Tarrida, J. R. Portillo. Basic exclusivity graphs in quantum correlations. Phys. Rev. A 88, 032104 (2013).","DOI":"10.1103\/PhysRevA.88.032104"},{"key":"13","unstructured":"A. Cabello. State-independent quantum contextuality and maximum nonlocality. arXiv:1112.5149 (2011)."},{"key":"14","unstructured":"F. Arends. A lower bound on the size of the smallest Kochen-Specker vector system. Master\u2019s thesis, Oxford University (2009)."},{"key":"15","doi-asserted-by":"publisher","unstructured":"F. Arends, J. Ouaknine, and C. W. Wampler. On Searching for Small Kochen-Specker Vector Systems. In: Kolman P., Kratochv\u00edl J. (eds) Graph-Theoretic Concepts in Computer Science. WG 2011. Lecture Notes in Computer Science, vol 6986. Springer, Berlin, Heidelberg (2011).","DOI":"10.1007\/978-3-642-25870-1_4"},{"key":"16","doi-asserted-by":"publisher","unstructured":"R. K. Clifton. Getting Contextual and Nonlocal Elements-of-Reality the Easy Way. American Journal of Physics, 61: 443 (1993).","DOI":"10.1119\/1.17239"},{"key":"17","doi-asserted-by":"publisher","unstructured":"A. Cabello, J. Estebaranz and G. Garc\u00eda-Alcaine. Bell-Kochen-Specker Theorem: A Proof with 18 vectors. Phys. Lett. A Vol. 212, Issue 4, 183 (1996).","DOI":"10.1016\/0375-9601(96)00134-X"},{"key":"18","unstructured":"C. Held. The Kochen-Specker Theorem. The Stanford Encyclopedia of Philosophy (Fall 2016 Edition), Edward N. Zalta (ed.), (2016)."},{"key":"19","doi-asserted-by":"publisher","unstructured":"A. Cabello. Experimentally Testable State-Independent Quantum Contextuality. Phys. Rev. Lett. 101, 210401 (2008).","DOI":"10.1103\/PhysRevLett.101.210401"},{"key":"20","doi-asserted-by":"publisher","unstructured":"A. Cabello and G. Garc\u00eda-Alcaine. Bell-Kochen-Specker Theorem for any finite dimension $n \\geq 3$. J. Phys A: Math. and Gen., 29, 1025, (1996).","DOI":"10.1088\/0305-4470\/29\/5\/016"},{"key":"21","doi-asserted-by":"publisher","unstructured":"I. Pitowsky. Infinite and finite Gleason's theorems and the logic of indeterminacy. Journal of Mathematical Physics 39, 218 (1998).","DOI":"10.1063\/1.532334"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1016\/j.shpsb.2003.10.002"},{"key":"23","doi-asserted-by":"crossref","unstructured":"A. M. Gleason. Measures on the Closed Subspaces of a Hilbert Space. Journal of Mathematics and Mechanics Vol. 6, No. 6, 885 (1957).","DOI":"10.1512\/iumj.1957.6.56050"},{"key":"24","doi-asserted-by":"publisher","unstructured":"S. Yu and C. H. Oh. State-Independent Proof of Kochen-Specker Theorem with 13 Rays. Phys. Rev. Lett. 108, 030402 (2012).","DOI":"10.1103\/PhysRevLett.108.030402"},{"key":"25","unstructured":"A. Stairs. Quantum Logic, Realism, and Value Definiteness. Philos. Sci. 50, 4, 578 (1983)."},{"key":"26","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press (2001)."},{"key":"27","doi-asserted-by":"publisher","unstructured":"L. Lovasz, M. Saks, A. Schrijver. Orthogonal representation and connectivity of graphs. Linear Algebra and its applications, 4, 114-115, 439 (1987).","DOI":"10.1016\/0024-3795(89)90475-8"},{"key":"28","unstructured":"R. Ramanathan, M. Horodecki, S. Pironio, K. Horodecki, and P. Horodecki. Generic randomness amplification schemes using Hardy paradoxes. arXiv: 1810.11648 (2018)."},{"key":"29","doi-asserted-by":"publisher","unstructured":"M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas. The strong perfect graph theorem. Annals of Mathematics, 164 (1): 51 (2006).","DOI":"10.4007\/annals.2006.164.51"},{"key":"30","doi-asserted-by":"publisher","unstructured":"R. Peeters. Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica 16, 3, 417 (1996).","DOI":"10.1007\/BF01261326"},{"key":"31","doi-asserted-by":"publisher","unstructured":"A Cabello and G Garcia-Alcaine. A hidden-variables versus quantum mechanics experiment. Journal of Phys. A: Math. and General, 28, No. 13 (1995).","DOI":"10.1088\/0305-4470\/28\/13\/016"},{"key":"32","doi-asserted-by":"publisher","unstructured":"P. Badzia\u0327g, I. Bengtsson, A. Cabello, and I. Pitowsky. Universality of State-Independent Violation of Correlation Inequalities for Noncontextual Theories. Phys. Rev. Lett. 103, 050401 (2009).","DOI":"10.1103\/PhysRevLett.103.050401"},{"key":"33","doi-asserted-by":"publisher","unstructured":"A. Cabello, J. R. Portillo, A. Sol\u00eds, 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).","DOI":"10.1103\/PhysRevA.98.012106"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-08-14-308\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T15:11:58Z","timestamp":1597417918000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-08-14-308\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,14]]},"references-count":34,"URL":"https:\/\/doi.org\/10.22331\/q-2020-08-14-308","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,14]]},"article-number":"308"}}