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

Abstract

We introduce two generalizations of Kochen-Specker (KS) sets: projective KS sets and generalized KS sets. We then use projective KS sets to characterize all 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 these two quantities, one can construct a classical channel for which entanglement assistance increases the one-shot zero-error capacity. As an example, we exhibit a new family of classical channels with an exponential increase.

16 pages

References in corpus (1)

• Gleason-Type Derivations of the Quantum Probability Rule for Generalized Measurements

Cited by in corpus (17)

• Applying the simplest Kochen-Specker set for quantum information processing
• Graph Homomorphisms for Quantum Players
• The status of determinism in proofs of the impossibility of a noncontextual model of quantum theory
• $\psi$-epistemic models are exponentially bad at explaining the distinguishability of quantum states
• Kochen-Specker set with seven contexts
• Binary Constraint System Games and Locally Commutative Reductions
• Beyond the Cabello-Severini-Winter framework: Making sense of contextuality without sharpness of measurements
• Noncontextuality Inequalities from Antidistinguishability
• Entanglement-assisted zero-error source-channel coding
• Separation between quantum Lovász number and entanglement-assisted zero-error classical capacity
• Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum Shannon capacities
• Exclusivity structures and graph representatives of local complementation orbits
• Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies
• Graph-theoretical Bounds on the Entangled Value of Non-local Games
• Counterexamples in self-testing
• Morphisms in categories of nonlocal games
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization