Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number

Giannicola Scarpa; Simone Severini

doi:10.1109/TIT.2011.2178018

paper

Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number

arXiv:1106.0712 · doi:10.1109/TIT.2011.2178018

Abstract

The quantum chromatic number of a graph $G$ is sandwiched between its chromatic number and its clique number, which are well known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number $χ_{q}^{(1)} (G)$ , which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number $χ (G)$ and the minimum dimension of orthogonal representations $ξ (G)$ . It is known that $ξ (G) \leq χ_{q}^{(1)} (G) \leq χ (G)$ . We answer three open questions about these relations: we give a necessary and sufficient condition to have $ξ (G) = χ_{q}^{(1)} (G)$ , we exhibit a class of graphs such that $ξ (G) < χ_{q}^{(1)} (G)$ , and we give a necessary and sufficient condition to have $χ_{q}^{(1)} (G) < χ (G)$ . Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of noncontextuality of physical theories, and more recently in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis, Hasegawa, Kikuchi, and Sasaki on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.

12 pages

References in corpus (1)

Improving zero-error classical communication with entanglement

Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number

Abstract

References in corpus (1)

Cited by in corpus (10)