1207.1111 (Laura Mancinska et al.)

A Generalization of Kochen-Specker Sets Relates Quantum Coloring to
Entanglement-Assisted Channel Capacity    [PDF]

Laura Mancinska, Giannicola Scarpa, Simone Severini

We introduce two generalizations of Kochen-Specker (KS) sets, namely projective KS sets and generalized KS sets. We then use projective KS sets to characterize all the graphs for which the chromatic number is strictly larger than the quantum chromatic number. Here the quantum chromatic number is defined via a nonlocal game based on graph coloring. We further show that from any graph with separation between its chromatic number and quantum chromatic number one can construct a classical channel for which entanglement assistance increases its one-shot zero-error capacity. As an example, we exhibit a new family of classical channels having a substantial increase.

View original: http://arxiv.org/abs/1207.1111