Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1807.00113 · Quantum

Gadget structures in proofs of the Kochen-Specker theorem

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

Published Aug 14, 2020• 18 citations
arXivHTMLPDF

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 \cite{Pitowsky}.

DOI
10.22331/q-2020-08-14-308

Related papers

Optimal measurement structures for contextuality applications

Yuan Liu, Ravishankar Ramanathan, Karol Horodecki +2 more

Abstract The Kochen-Specker (KS) theorem is a corner-stone result in the foundations of quantum mechanics describing the fundamental difference between quantum theory and classical non-contextual theories. Recently specific substructures termed $01$-gadgets were shown to exist within KS proofs that capture the essential contradiction of the theorem. Here, we show these gadgets and their generalizations provide an optimal toolbox for contextuality applications including (i) constructing classical channels exhibiting entanglement-assisted advantage in zero-error communication, (ii) identifying large separations between quantum theory and binary generalised probabilistic theories, and (iii) finding optimal tests for contextuality-based semi-device-independent randomness generation. Furthermore, we introduce and study a generalisation to definite prediction sets for more general logical propositions, that we term higher-order gadgets. We pinpoint the role these higher-order gadgets play in KS proofs by identifying these as induced subgraphs within KS graphs and showing how to construct proofs of state-independent contextuality using higher-order gadgets as building blocks. The constructions developed here may help in solving some of the remaining open problems regarding minimal proofs of the Kochen-Specker theorem.

arXiv:2206.13139•npj Quantum Information•Jun 29, 2023•3 citations

Large violations in Kochen Specker contextuality and their applications

Ravishankar Ramanathan, Yuan Liu, Paweł Horodecki

Abstract It is of interest to study how contextual quantum mechanics is, in terms of the violation of Kochen Specker state-independent and state-dependent non-contextuality inequalities. We present state-independent non-contextuality inequalities with large violations, in particular, we exploit a connection between Kochen–Specker proofs and pseudo-telepathy games to show KS proofs in Hilbert spaces of dimension d ⩾ 217 with the ratio of quantum value to classical bias being O ( d / log d ) . We study the properties of this KS set and show applications of the large violation. It has been recently shown that Kochen–Specker proofs always consist of substructures of state-dependent contextuality proofs called 01-gadgets. We show a one-to-one connection between 01-gadgets in C d and Hardy paradoxes for the maximally entangled state in C d ⊗ C d . We use this connection to construct large violation 01-gadgets between arbitrary vectors in C d , as well as novel Hardy paradoxes for the maximally entangled state in C d ⊗ C d , and give applications of these constructions. As a technical result, we show that the minimum dimension of the faithful orthogonal representation of a graph in R d is not a graph monotone, a result that may be of independent interest.

arXiv:2106.15954•New Journal of Physics•Nov 17, 2021•3 citations

Kochen-Specker theorem revisited

Del Rajan, Matt Visser

The Kochen-Specker theorem is a basic and fundamental 50 year old non-existence result affecting the foundations of quantum mechanix, strongly implying the lack of any meaningful notion of "quantum realism", and typically leading to discussions of "contextuality" in quantum physics. Original proofs of the Kochen-Specker theorem proceeded via brute force counter-examples; often quite complicated and subtle (albeit mathematically "elementary") counter-examples. Only more recently have somewhat more "geometrical" proofs been developed. We present herein yet another simplified geometrical proof of the Kochen-Specker theorem, one that is valid for any number of dimensions, that minimizes the technical machinery involved, and makes the seriousness of the issues raised manifest.

arXiv:1708.01380•Aug 4, 2017•5 citations

Contextualism And Nonlocality In Quantum Mechanics

Michael William Kernaghan

I describe the conceptual problems associated with the Kochen-Specker theorem including the presuppositions of the theorem and plausible interpretations of the conclusions motivated by the theorem. I describe an idealized quantum system which demonstrates both the Kochen-Specker theorem and the Bell argument for nonlocality. I present new findings about the mathematical structures which support a proof of the Kochen-Specker theorem.

•Jan 1, 1995•1 citation

Proofs of the Kochen-Specker theorem based on the N -qubit Pauli group

Mordecai Waegell, P. K. Aravind

We present a number of observables-based proofs of the Kochen-Specker (KS) theorem based on the $N$-qubit Pauli group for $N\ensuremath{\ge}4$, thus adding to the proofs that have been presented earlier for the 2- and 3-qubit groups. These proofs have the attractive feature that they can be presented in the form of diagrams from which they are obvious by inspection. They are also irreducible in the sense that they cannot be reduced to smaller proofs by ignoring some subset of qubits and/or observables in them. A simple algorithm is given for transforming any observables-based KS proof into a large number of projectors-based KS proofs; if the observables-based proof has $O$ observables, with each observable occurring in exactly two commuting sets and any two commuting sets having at most one observable in common, the number of associated projectors-based parity proofs is 2${}^{O}$. We introduce symbols for the observables- and projectors-based KS proofs that capture their important features and also convey a feeling for the enormous variety of both these types of proofs within the $N$-qubit Pauli group. We discuss an infinite family of observables-based proofs, whose members include all numbers of qubits from 2 up, and show how it can be used to generate projectors-based KS proofs involving only 9 bases (or experimental contexts) in any dimension of the form ${2}^{N}$ for $N\ensuremath{\ge}2$. Some implications of our results are discussed.

arXiv:1302.4801•Physical Review A•Jul 1, 2013•33 citations

Kochen-Specker Theorem and Games

Laura Mančinska

One of the statements one would hear pretty early in any quantum mechanics course is that for quantum particles there are properties which do not have definite values. For example, if we measure |+〉 in standard basis, the best we can do to describe the outcome is to say, that with probability 1/2 we will get 0 and with probability 1/2 we will get 1. Yet one could wonder, is this really the way things are or is it just because our description of this quantum particle is incomplete, but in fact there are some hidden variables inside every quantum system that contain enough information to tell the outcome of measurement (see Fig. 1). However, many people disdain the idea of hidden variables, so there has been rather long history of theorems that forbid theories involving hidden variables. Usually if one wants to prove some no hidden variables theorem he has to assume something about the hidden variables theories he is going to forbid. One of such assumptions is non-contextuality, which means that the outcome we get after measuring with an observable is the same regardless of what other observables we choose to measure at the same time. The first theorem forbidding hidden variables theories is due to von Neumann in 1932. Then for a third of a century everyone cited von Neumann’s work carelessly, till Bell in 1966 indicated that there was an unreasonable assumption in von Neumann’s proof and urged for further examination of the problem (see [6] and [1] for more historical details). Bell also constructed a hidden variables model for one qubit that could assign the outcome of any observable in a way consistent with quantum mechanics. He also proved two theorems that forbid non-contextual hidden variables theories using counterexamples with larger quantum systems. Yet surprisingly he himself thought that hidden variables do exists and considered these theorems only as characterizations of the hidden variables theory we should look for. In this essay we will discuss several versions of one of the two Bell’s theorems. The theorem we will consider was also independently proven by Kochen and Specker in 1967 (see [5]), hence it is called Bell-Kochen-Specker theorem. For shortness and in order not to mix this theorem with another Bell’s theorem from now on we will refer to it as Kochen-Specker theorem. We will be interested in proving several versions of this theorem and the following lemma will turn out to be of great use:

•Jan 1, 2007•0 citations
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 \cite{Pitowsky}.
Abstract The Kochen-Specker (KS) theorem is a corner-stone result in the foundations of quantum mechanics describing the fundamental difference between quantum theory and classical non-contextual theories. Recently specific substructures termed 010101-gadgets were shown to exist within KS proofs that capture the essential contradiction of the theorem. Here, we show these gadgets and their generalizations provide an optimal toolbox for contextuality applications including (i) constructing classical channels exhibiting entanglement-assisted advantage in zero-error communication, (ii) identifying large separations between quantum theory and binary generalised probabilistic theories, and (iii) finding optimal tests for contextuality-based semi-device-independent randomness generation. Furthermore, we introduce and study a generalisation to definite prediction sets for more general logical propositions, that we term higher-order gadgets. We pinpoint the role these higher-order gadgets play in KS proofs by identifying these as induced subgraphs within KS graphs and showing how to construct proofs of state-independent contextuality using higher-order gadgets as building blocks. The constructions developed here may help in solving some of the remaining open problems regarding minimal proofs of the Kochen-Specker theorem.
Abstract It is of interest to study how contextual quantum mechanics is, in terms of the violation of Kochen Specker state-independent and state-dependent non-contextuality inequalities. We present state-independent non-contextuality inequalities with large violations, in particular, we exploit a connection between Kochen–Specker proofs and pseudo-telepathy games to show KS proofs in Hilbert spaces of dimension d ⩾ 217 with the ratio of quantum value to classical bias being O ( d / log d ) . We study the properties of this KS set and show applications of the large violation. It has been recently shown that Kochen–Specker proofs always consist of substructures of state-dependent contextuality proofs called 01-gadgets. We show a one-to-one connection between 01-gadgets in C d and Hardy paradoxes for the maximally entangled state in C d ⊗ C d . We use this connection to construct large violation 01-gadgets between arbitrary vectors in C d , as well as novel Hardy paradoxes for the maximally entangled state in C d ⊗ C d , and give applications of these constructions. As a technical result, we show that the minimum dimension of the faithful orthogonal representation of a graph in R d is not a graph monotone, a result that may be of independent interest.
The Kochen-Specker theorem is a basic and fundamental 50 year old non-existence result affecting the foundations of quantum mechanix, strongly implying the lack of any meaningful notion of "quantum realism", and typically leading to discussions of "contextuality" in quantum physics. Original proofs of the Kochen-Specker theorem proceeded via brute force counter-examples; often quite complicated and subtle (albeit mathematically "elementary") counter-examples. Only more recently have somewhat more "geometrical" proofs been developed. We present herein yet another simplified geometrical proof of the Kochen-Specker theorem, one that is valid for any number of dimensions, that minimizes the technical machinery involved, and makes the seriousness of the issues raised manifest.
We present a number of observables-based proofs of the Kochen-Specker (KS) theorem based on the NNN-qubit Pauli group for $N\ensuremath{\ge}4$, thus adding to the proofs that have been presented earlier for the 2- and 3-qubit groups. These proofs have the attractive feature that they can be presented in the form of diagrams from which they are obvious by inspection. They are also irreducible in the sense that they cannot be reduced to smaller proofs by ignoring some subset of qubits and/or observables in them. A simple algorithm is given for transforming any observables-based KS proof into a large number of projectors-based KS proofs; if the observables-based proof has OOO observables, with each observable occurring in exactly two commuting sets and any two commuting sets having at most one observable in common, the number of associated projectors-based parity proofs is 2O{}^{O}O. We introduce symbols for the observables- and projectors-based KS proofs that capture their important features and also convey a feeling for the enormous variety of both these types of proofs within the NNN-qubit Pauli group. We discuss an infinite family of observables-based proofs, whose members include all numbers of qubits from 2 up, and show how it can be used to generate projectors-based KS proofs involving only 9 bases (or experimental contexts) in any dimension of the form 2N{2}^{N}2N for $N\ensuremath{\ge}2$. Some implications of our results are discussed.
One of the statements one would hear pretty early in any quantum mechanics course is that for quantum particles there are properties which do not have definite values. For example, if we measure |+〉 in standard basis, the best we can do to describe the outcome is to say, that with probability 1/2 we will get 0 and with probability 1/2 we will get 1. Yet one could wonder, is this really the way things are or is it just because our description of this quantum particle is incomplete, but in fact there are some hidden variables inside every quantum system that contain enough information to tell the outcome of measurement (see Fig. 1). However, many people disdain the idea of hidden variables, so there has been rather long history of theorems that forbid theories involving hidden variables. Usually if one wants to prove some no hidden variables theorem he has to assume something about the hidden variables theories he is going to forbid. One of such assumptions is non-contextuality, which means that the outcome we get after measuring with an observable is the same regardless of what other observables we choose to measure at the same time. The first theorem forbidding hidden variables theories is due to von Neumann in 1932. Then for a third of a century everyone cited von Neumann’s work carelessly, till Bell in 1966 indicated that there was an unreasonable assumption in von Neumann’s proof and urged for further examination of the problem (see [6] and [1] for more historical details). Bell also constructed a hidden variables model for one qubit that could assign the outcome of any observable in a way consistent with quantum mechanics. He also proved two theorems that forbid non-contextual hidden variables theories using counterexamples with larger quantum systems. Yet surprisingly he himself thought that hidden variables do exists and considered these theorems only as characterizations of the hidden variables theory we should look for. In this essay we will discuss several versions of one of the two Bell’s theorems. The theorem we will consider was also independently proven by Kochen and Specker in 1967 (see [5]), hence it is called Bell-Kochen-Specker theorem. For shortness and in order not to mix this theorem with another Bell’s theorem from now on we will refer to it as Kochen-Specker theorem. We will be interested in proving several versions of this theorem and the following lemma will turn out to be of great use: