A Kochen-Specker system has at least 22 vectors (extended abstract)

Sander Uijlen
(Radboud Universiteit)
Bas Westerbaan
(Radboud Universiteit)

At the heart of the Conway-Kochen Free Will theorem and Kochen and Specker's argument against non- contextual hidden variable theories is the existence of a Kochen-Specker (KS) system: a set of points on the sphere that has no 0,1-coloring such that at most one of two orthogonal points are colored 1 and of three pairwise orthogonal points exactly one is colored 1. In public lectures, Conway encour- aged the search for small KS systems. At the time of writing, the smallest known KS system has 31 vectors. Arends, Ouaknine and Wampler have shown that a KS system has at least 18 vectors, by reducing the problem to the existence of graphs with a topological embeddability and non-colorability prop- erty. The bottleneck in their search proved to be the sheer number of graphs on more than 17 vertices and deciding embeddability.

Continuing their effort, we prove a restriction on the class of graphs we need to consider and develop a more practical decision procedure for embeddability to improve the lower bound to 22.

In Bob Coecke, Ichiro Hasuo and Prakash Panangaden: Proceedings of the 11th workshop on Quantum Physics and Logic (QPL 2014), Kyoto, Japan, 4-6th June 2014, Electronic Proceedings in Theoretical Computer Science 172, pp. 154–164.
Published: 28th December 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.172.11 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org