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:1401.3035

Generalized parity proofs of the Kochen-Specker theorem

Petr Lisoněk, Robert Raussendorf, Vijaykumar Singh

Published Jan 13, 2014• 4 citations
arXivHTMLPDF

Abstract

We discuss two approaches to producing generalized parity proofs of the Kochen-Specker theorem. Such proofs use contexts of observables whose product is $I$ or $-I$; we call them constraints. In the first approach, one starts with a fixed set of constraints and methods of linear algebra are used to produce subsets that are generalized parity proofs. Coding theory methods are used for enumeration of the proofs by size. In the second approach, one starts with the combinatorial structure of the set of constraints and one looks for ways to suitably populate this structure with observables. As well, we are able to show that many combinatorial structures can not produce parity proofs.

DOI
10.48550/arxiv.1401.3035

Related papers

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

Proofs of the Kochen–Specker theorem based on a system of three qubits

Mordecai Waegell, P. K. Aravind

A number of new proofs of the Kochen–Specker theorem are given based on the observables of the three-qubit Pauli group. Each proof is presented in the form of a diagram from which it is obvious by inspection. Each of our observable-based proofs leads to a system of projectors and bases that generally yields a large number of ‘parity proofs’ of the Kochen–Specker theorem. Some examples of such proofs are given and some of their applications are discussed.

arXiv:1205.5015•Journal of Physics A Mathematical and Theoretical•Sep 18, 2012•44 citations

Generalized Kochen-Specker theorem

P. K. Aravind

A proof of the generalized Kochen-Specker theorem in two dimensions due to Cabello and Nakamura [A. Cabello, Phys. Rev. Lett. 90, 190401 (2003)] is extended to all higher dimensions. A set of 18 states in four dimensions is used to give closely related proofs of the generalized Kochen-Specker, Kochen-Specker, and Bell theorems that shed some light on the relationship between these three theorems.

arXiv:quant-ph/0301074•Physical Review A•Nov 17, 2003•16 citations

Triacontagonal proofs of the Bell–Kochen–Specker theorem

P. K. Aravind, Justin Y. J. Burton, Guillermo Nuñez Ponasso +1 more

Abstract Coxeter pointed out that a number of polytopes can be projected orthogonally into two dimensions in such a way that their vertices lie on a number of concentric regular triacontagons (or 30-gons). Among them are the 600-cell and 120-cell in four dimensions and Gosset’s polytope 4 21 in eight dimensions. We show how these projections can be modified into Kochen–Specker diagrams from which parity proofs of the Bell–Kochen–Specker theorem are easily extracted. Our construction trivially yields parity proofs of fifteen bases for all three polytopes and also allows many other proofs of the same type to be constructed for two of them. The defining feature of these proofs is that they have a fifteen-fold symmetry about the center of the Kochen–Specker diagram and thus involve both rays and bases that are multiples of fifteen. Any proof of this type can be written as a word made up of an odd number of distinct letters, each representing an orbit of fifteen bases. Knowing the word representing a proof makes it possible to infer all its characteristics without first having to recover its bases. A comparison is made with earlier approaches that have been used to obtain parity proofs in these polytopes, and some directions in which this work can be extended are discussed.

arXiv:2510.01063•Journal of Physics A Mathematical and Theoretical•Mar 23, 2026•0 citations

Parity proofs of the Kochen–Specker theorem based on the Lie algebra E8

Mordecai Waegell, P K Aravind

The 240 root vectors of the Lie algebra E8 lead to a system of 120 rays in a real eight-dimensional Hilbert space that contains a large number of parity proofs of the Kochen–Specker (KS) theorem. After introducing the rays in a triacontagonal representation due to Coxeter, we present their KS diagram in the form of a 'basis table' showing all 2025 bases (i.e., sets of eight mutually orthogonal rays) formed by the rays. Only a few of the bases are actually listed, but simple rules are given, based on the symmetries of E8, for obtaining all the other bases from the ones shown. The basis table is an object of great interest because all the parity proofs of E8 can be exhibited as subsets of it. We show how the triacontagonal representation of E8 facilitates the identification of substructures that are more easily searched for their parity proofs. We have found hundreds of different types of parity proofs, ranging from 9 bases (or contexts) at the low end to 35 bases at the high end, and involving projectors of various ranks and multiplicities. After giving an overview of the proofs we found, we present a few concrete examples of the proofs that illustrate both their generic features as well as some of their more unusual properties. In particular, we present a proof involving 34 rays and 9 bases that appears to provide the most compact proof of the KS theorem found to date in eight-dimensions.

arXiv:1502.04350•Journal of Physics A Mathematical and Theoretical•May 14, 2015•21 citations

Kochen-Specker set with seven contexts

Petr Lisoněk, Piotr Badziąg, José R. Portillo +1 more

The Kochen-Specker (KS) theorem is a central result in quantum theory and has applications in quantum information. Its proof requires several yes-no tests that can be grouped in contexts or subsets of jointly measurable tests. Arguably, the best measure of simplicity of a KS set is the number of contexts. The smaller this number is, the smaller the number of experiments needed to reveal the conflict between quantum theory and noncontextual theories and to get a quantum vs classical outperformance. The original KS set had 132 contexts. Here we introduce a KS set with seven contexts and prove that this is the simplest KS set that admits a symmetric parity proof.

arXiv:1308.6012•Physical Review A•Apr 1, 2014•52 citations
We discuss two approaches to producing generalized parity proofs of the Kochen-Specker theorem. Such proofs use contexts of observables whose product is III or −I-I−I; we call them constraints. In the first approach, one starts with a fixed set of constraints and methods of linear algebra are used to produce subsets that are generalized parity proofs. Coding theory methods are used for enumeration of the proofs by size. In the second approach, one starts with the combinatorial structure of the set of constraints and one looks for ways to suitably populate this structure with observables. As well, we are able to show that many combinatorial structures can not produce parity proofs.
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.
Abstract Coxeter pointed out that a number of polytopes can be projected orthogonally into two dimensions in such a way that their vertices lie on a number of concentric regular triacontagons (or 30-gons). Among them are the 600-cell and 120-cell in four dimensions and Gosset’s polytope 4 21 in eight dimensions. We show how these projections can be modified into Kochen–Specker diagrams from which parity proofs of the Bell–Kochen–Specker theorem are easily extracted. Our construction trivially yields parity proofs of fifteen bases for all three polytopes and also allows many other proofs of the same type to be constructed for two of them. The defining feature of these proofs is that they have a fifteen-fold symmetry about the center of the Kochen–Specker diagram and thus involve both rays and bases that are multiples of fifteen. Any proof of this type can be written as a word made up of an odd number of distinct letters, each representing an orbit of fifteen bases. Knowing the word representing a proof makes it possible to infer all its characteristics without first having to recover its bases. A comparison is made with earlier approaches that have been used to obtain parity proofs in these polytopes, and some directions in which this work can be extended are discussed.
The 240 root vectors of the Lie algebra E8 lead to a system of 120 rays in a real eight-dimensional Hilbert space that contains a large number of parity proofs of the Kochen–Specker (KS) theorem. After introducing the rays in a triacontagonal representation due to Coxeter, we present their KS diagram in the form of a 'basis table' showing all 2025 bases (i.e., sets of eight mutually orthogonal rays) formed by the rays. Only a few of the bases are actually listed, but simple rules are given, based on the symmetries of E8, for obtaining all the other bases from the ones shown. The basis table is an object of great interest because all the parity proofs of E8 can be exhibited as subsets of it. We show how the triacontagonal representation of E8 facilitates the identification of substructures that are more easily searched for their parity proofs. We have found hundreds of different types of parity proofs, ranging from 9 bases (or contexts) at the low end to 35 bases at the high end, and involving projectors of various ranks and multiplicities. After giving an overview of the proofs we found, we present a few concrete examples of the proofs that illustrate both their generic features as well as some of their more unusual properties. In particular, we present a proof involving 34 rays and 9 bases that appears to provide the most compact proof of the KS theorem found to date in eight-dimensions.
The Kochen-Specker (KS) theorem is a central result in quantum theory and has applications in quantum information. Its proof requires several yes-no tests that can be grouped in contexts or subsets of jointly measurable tests. Arguably, the best measure of simplicity of a KS set is the number of contexts. The smaller this number is, the smaller the number of experiments needed to reveal the conflict between quantum theory and noncontextual theories and to get a quantum vs classical outperformance. The original KS set had 132 contexts. Here we introduce a KS set with seven contexts and prove that this is the simplest KS set that admits a symmetric parity proof.