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:quant-ph/0409014 · Journal of Physics A Mathematical and General

Kochen–Specker vectors

Mladen Pavičić, Jean‐Pierre Merlet, Brendan McKay, Norman D Megill

Published Feb 3, 2005• 79 citations
arXivHTMLPDF

Abstract

We give a constructive and exhaustive definition of Kochen–Specker (KS) vectors in a Hilbert space of any dimension as well as of all the remaining vectors of the space. KS vectors are elements of any set of orthonormal states, i.e., vectors in an n -dimensional Hilbert space, , to which it is impossible to assign 1s and 0s in such a way that no two mutually orthogonal vectors from the set are both assigned 1 and that not all mutually orthogonal vectors are assigned 0. Our constructive definition of such KS vectors is based on algorithms that generate MMP diagrams corresponding to blocks of orthogonal vectors in , on algorithms that single out those diagrams on which algebraic 0 – 1 states cannot be defined, and on algorithms that solve nonlinear equations describing the orthogonalities of the vectors by means of statistically polynomially complex interval analysis and self-teaching programs. The algorithms are limited neither by the number of dimensions nor by the number of vectors. To demonstrate the power of the algorithms, all four-dimensional KS vector systems containing up to 24 vectors were generated and described, all three-dimensional vector systems containing up to 30 vectors were scanned, and several general properties of KS vectors were found.

DOI
10.1088/0305-4470/38/7/013

Related papers

Kochen-Specker Algorithms for Qubits

Mladen Pavičić

Algorithms for finding arbitrary sets of Kochen‐Specker (KS) qubits as well as all the remaining vectors in a space of an arbitrary dimension are presented. The algorithms are based on linear MMP diagrams which generate orthogonalities of KS qubits, on an algebraic definition of states on the diagrams, and on nonlinear equations corresponding to MMP diagrams whose solutions are either KS qubits or the remaining vectors of a chosen space depending on whether the diagrams allow 0–1 states or not. The complexity of the algorithms is polynomial. New results obtained with the help of the algorithms are presented.

arXiv:quant-ph/0412197•AIP conference proceedings•Jan 1, 2004•5 citations

On Searching for Small Kochen-Specker Vector Systems (extended version)

Felix Arends, Joël Ouaknine, Charles W. Wampler

Kochen-Specker (KS) vector systems are sets of vectors in R^3 with the property that it is impossible to assign 0s and 1s to the vectors in such a way that no two orthogonal vectors are assigned 0 and no three mutually orthogonal vectors are assigned 1. The existence of such sets forms the basis of the Kochen-Specker and Free Will theorems. Currently, the smallest known KS vector system contains 31 vectors. In this paper, we establish a lower bound of 18 on the size of any KS vector system. This requires us to consider a mix of graph-theoretic and topological embedding problems, which we investigate both from theoretical and practical angles. We propose several algorithms to tackle these problems and report on extensive experiments. At the time of writing, a large gap remains between the best lower and upper bounds for the minimum size of KS vector systems.

arXiv:1111.3301•Nov 14, 2011•2 citations

Proving Kochen-Specker Theorem Using Projection Measurement and Positive Operator-Valued Measure

S. P. Toh

One of the main theorems on the impossibility of hidden variables in quantum mechanics is Kochen-Specker theorem (KS). This theorem says that any hidden variable theory that satisfies quantum mechanics must be contextual. More specifically, it asserts that, in Hilbert space of dimension ≥ 3, it is impossible to associate definite numerical values, 1 or 0, with every projection operator Pm, in such a way that, if a set of commuting Pm satisfies 1=ΣmP, the corresponding values will also satisfy . Since the first proof of Kochen and Specker using 117 vectors in R3, there were many attempts to reduce the number of vector either via conceiving ingenious models or extending the system being considered to higher dimension. By considering eight dimensional three qubits system, we found a state dependent proof that requires only five vectors. The state that we assign value of 1 is the ray that arises from intersection of two planes. The recent advancements show that the KS theorem proof can be extended to two dimensional quantum system through generalized measurement represented by positive operator-valued measured (POVM). In POVMs the number of available outcomes of a measurement may be higher than the dimensionality of the Hilbert space and N-outcome generalized measurement is represented by N-element POVM which consists of N positive semidefinite operators {}dE that sum to identity. Each pair of elements is not mutually orthogonal if the number of outcome of measurements is bigger than the dimensionality. In terms of POVM, Kochen-Specker theorem asserts that and could not be satisfied for . We developed a general model that enables us to generate different sizes of the POVM for the proof of the Kochen-Specker theorem. We show that the current simplest Nakamura model is in fact a special case of our model. W also provide another model which is as simple as the Nakamura’s but consists of different sets of POVM.

•Jan 1, 2008•0 citations

Vector Generation of Quantum Contextual Sets in Even Dimensional Hilbert Spaces

Mladen Pavičić, Norman D. Megill

Recently, quantum contextuality has been proved to be the source of quantum computation's power. That, together with multiple recent contextual experiments, prompts improving the methods of generation of contextual sets and finding their features. The most elaborated contextual sets, which offer blueprints for contextual experiments and computational gates, are the Kochen-Specker (KS) sets. In this paper, we show a method of vector generation that supersedes previous methods. It is implemented by means of algorithms and programs that generate hypergraphs embodying the Kochen-Specker property and that are designed to be carried out on supercomputers. We show that vector component generation of KS hypergraphs exhausts all possible vectors that can be constructed from chosen vector components, in contrast to previous studies that used incomplete lists of vectors and therefore missed a majority of hypergraphs. Consequently, this unified method is far more efficient for generations of KS sets and their implementation in quantum computation and quantum communication. Several new KS classes and their features have been found and are elaborated on in the paper. Greechie diagrams are discussed.

arXiv:1905.01567•Entropy•Dec 5, 2018•18 citations

New class of 4-dim Kochen–Specker sets

Mladen Pavičić, Norman D. Megill, P. K. Aravind +1 more

We find a new highly symmetrical and very numerous class (millions of nonisomorphic sets) of 4-dim Kochen–Specker (KS) vector sets. Due to the nature of their geometrical symmetries, they cannot be obtained from previously known ones. We generate the sets from a single set of 60 orthogonal spin vectors and 75 of their tetrads (which we obtained from the 600-cell) by means of our newly developed stripping technique. We also consider critical KS subsets and analyze their geometry. The algorithms and programs for the generation of our KS sets are presented.

arXiv:1004.1433•Journal of Mathematical Physics•Feb 1, 2011•17 citations

On Critical Kochen-Specker Sets

Mladen Pavičić, Norman D. Megill, P. K. Aravind

We find a new highly symmetrical and very numerous class (millions of non-isomorphic sets) of 4-dim Kochen-Specker (KS) vector sets. Due to the nature of their geometrical symmetries, they cannot be obtained from previously known ones. We generate the sets from a single set of 60 orthogonal spin vectors and 75 of their tetrads (which we obtained from the 600-cell) by means of our newly developed stripping technique. We also consider critical KS subsets and analyze their geometry. The algorithms and programs for the generation of our KS sets are presented.

•Apr 8, 2010•1 citation
We give a constructive and exhaustive definition of Kochen–Specker (KS) vectors in a Hilbert space of any dimension as well as of all the remaining vectors of the space. KS vectors are elements of any set of orthonormal states, i.e., vectors in an n -dimensional Hilbert space, , to which it is impossible to assign 1s and 0s in such a way that no two mutually orthogonal vectors from the set are both assigned 1 and that not all mutually orthogonal vectors are assigned 0. Our constructive definition of such KS vectors is based on algorithms that generate MMP diagrams corresponding to blocks of orthogonal vectors in , on algorithms that single out those diagrams on which algebraic 0 – 1 states cannot be defined, and on algorithms that solve nonlinear equations describing the orthogonalities of the vectors by means of statistically polynomially complex interval analysis and self-teaching programs. The algorithms are limited neither by the number of dimensions nor by the number of vectors. To demonstrate the power of the algorithms, all four-dimensional KS vector systems containing up to 24 vectors were generated and described, all three-dimensional vector systems containing up to 30 vectors were scanned, and several general properties of KS vectors were found.
Algorithms for finding arbitrary sets of Kochen‐Specker (KS) qubits as well as all the remaining vectors in a space of an arbitrary dimension are presented. The algorithms are based on linear MMP diagrams which generate orthogonalities of KS qubits, on an algebraic definition of states on the diagrams, and on nonlinear equations corresponding to MMP diagrams whose solutions are either KS qubits or the remaining vectors of a chosen space depending on whether the diagrams allow 0–1 states or not. The complexity of the algorithms is polynomial. New results obtained with the help of the algorithms are presented.
Kochen-Specker (KS) vector systems are sets of vectors in R^3 with the property that it is impossible to assign 0s and 1s to the vectors in such a way that no two orthogonal vectors are assigned 0 and no three mutually orthogonal vectors are assigned 1. The existence of such sets forms the basis of the Kochen-Specker and Free Will theorems. Currently, the smallest known KS vector system contains 31 vectors. In this paper, we establish a lower bound of 18 on the size of any KS vector system. This requires us to consider a mix of graph-theoretic and topological embedding problems, which we investigate both from theoretical and practical angles. We propose several algorithms to tackle these problems and report on extensive experiments. At the time of writing, a large gap remains between the best lower and upper bounds for the minimum size of KS vector systems.
One of the main theorems on the impossibility of hidden variables in quantum mechanics is Kochen-Specker theorem (KS). This theorem says that any hidden variable theory that satisfies quantum mechanics must be contextual. More specifically, it asserts that, in Hilbert space of dimension ≥ 3, it is impossible to associate definite numerical values, 1 or 0, with every projection operator Pm, in such a way that, if a set of commuting Pm satisfies 1=ΣmP, the corresponding values will also satisfy . Since the first proof of Kochen and Specker using 117 vectors in R3, there were many attempts to reduce the number of vector either via conceiving ingenious models or extending the system being considered to higher dimension. By considering eight dimensional three qubits system, we found a state dependent proof that requires only five vectors. The state that we assign value of 1 is the ray that arises from intersection of two planes. The recent advancements show that the KS theorem proof can be extended to two dimensional quantum system through generalized measurement represented by positive operator-valued measured (POVM). In POVMs the number of available outcomes of a measurement may be higher than the dimensionality of the Hilbert space and N-outcome generalized measurement is represented by N-element POVM which consists of N positive semidefinite operators {}dE that sum to identity. Each pair of elements is not mutually orthogonal if the number of outcome of measurements is bigger than the dimensionality. In terms of POVM, Kochen-Specker theorem asserts that and could not be satisfied for . We developed a general model that enables us to generate different sizes of the POVM for the proof of the Kochen-Specker theorem. We show that the current simplest Nakamura model is in fact a special case of our model. W also provide another model which is as simple as the Nakamura’s but consists of different sets of POVM.
Recently, quantum contextuality has been proved to be the source of quantum computation's power. That, together with multiple recent contextual experiments, prompts improving the methods of generation of contextual sets and finding their features. The most elaborated contextual sets, which offer blueprints for contextual experiments and computational gates, are the Kochen-Specker (KS) sets. In this paper, we show a method of vector generation that supersedes previous methods. It is implemented by means of algorithms and programs that generate hypergraphs embodying the Kochen-Specker property and that are designed to be carried out on supercomputers. We show that vector component generation of KS hypergraphs exhausts all possible vectors that can be constructed from chosen vector components, in contrast to previous studies that used incomplete lists of vectors and therefore missed a majority of hypergraphs. Consequently, this unified method is far more efficient for generations of KS sets and their implementation in quantum computation and quantum communication. Several new KS classes and their features have been found and are elaborated on in the paper. Greechie diagrams are discussed.
We find a new highly symmetrical and very numerous class (millions of nonisomorphic sets) of 4-dim Kochen–Specker (KS) vector sets. Due to the nature of their geometrical symmetries, they cannot be obtained from previously known ones. We generate the sets from a single set of 60 orthogonal spin vectors and 75 of their tetrads (which we obtained from the 600-cell) by means of our newly developed stripping technique. We also consider critical KS subsets and analyze their geometry. The algorithms and programs for the generation of our KS sets are presented.
We find a new highly symmetrical and very numerous class (millions of non-isomorphic sets) of 4-dim Kochen-Specker (KS) vector sets. Due to the nature of their geometrical symmetries, they cannot be obtained from previously known ones. We generate the sets from a single set of 60 orthogonal spin vectors and 75 of their tetrads (which we obtained from the 600-cell) by means of our newly developed stripping technique. We also consider critical KS subsets and analyze their geometry. The algorithms and programs for the generation of our KS sets are presented.