Physics – Quantum Physics
Scientific paper
2011-06-03
IEEE Transactions on Information Theory, vol. 58, no. 4, April 2012
Physics
Quantum Physics
12 pages
Scientific paper
10.1109/TIT.2011.2178018
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 $\chi_q^{(1)}(G)$, which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number $\chi(G)$ and the minimum dimension of orthogonal representations $\xi(G)$. It is known that $\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)$. We answer three open questions about these relations: we give a necessary and sufficient condition to have $\xi(G) = \chi_q^{(1)}(G)$, we exhibit a class of graphs such that $\xi(G) < \chi_q^{(1)}(G)$, and we give a necessary and sufficient condition to have $\chi_q^{(1)}(G) < \chi(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.
Scarpa Giannicola
Severini Simone
No associations
LandOfFree
Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-224234