A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity
arXiv:1207.1111 · doi:10.1109/TIT.2013.2248031
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.
arXiv comment16 pages
References in corpus (11)
- Bell-Kochen-Specker theorem: A proof with 18 vectors
- Quantum states and generalized observables: a simple proof of Gleason's theorem
- Quantum Pseudo-Telepathy
- Improving zero-error classical communication with entanglement
- Gleason-Type Derivations of the Quantum Probability Rule for Generalized Measurements
- Kochen-Specker theorem for a single qubit using positive operator-valued measures
- A quantum protocol to win the graph colouring game on all Hadamard graphs
- Entanglement can increase asymptotic rates of zero-error classical communication over classical channels
- Entanglement-assisted zero-error capacity is upper bounded by the Lovasz theta function
- Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number
- A note on the stability number of an orthogonality graph
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
- -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