Exclusivity structures and graph representatives of local complementation orbits
arXiv:1211.4250 · doi:10.1063/1.4813438
Abstract
We describe a construction that maps any connected graph G on three or more vertices into a larger graph, H(G), whose independence number is strictly smaller than its Lovász number which is equal to its fractional packing number. The vertices of H(G) represent all possible events consistent with the stabilizer group of the graph state associated with G, and exclusive events are adjacent. Mathematically, the graph H(G) corresponds to the orbit of G under local complementation. Physically, the construction translates into graph-theoretic terms the connection between a graph state and a Bell inequality maximally violated by quantum mechanics. In the context of zero-error information theory, the construction suggests a protocol achieving the maximum rate of entanglement-assisted capacity, a quantum mechanical analogue of the Shannon capacity, for each H(G). The violation of the Bell inequality is expressed by the one-shot version of this capacity being strictly larger than the independence number. Finally, given the correspondence between graphs and exclusivity structures, we are able to compute the independence number for certain infinite families of graphs with the use of quantum non-locality, therefore highlighting an application of quantum theory in the proof of a purely combinatorial statement.
arXiv comment20 pages, 1 figure
References in corpus (16)
- Measurement-based quantum computation with cluster states
- Multi-party entanglement in graph states
- Quantum Error Correction and Orthogonal Geometry
- Quantum error-correcting codes associated with graphs
- Graphical description of the action of local Clifford transformations on graph states
- Bell Inequalities for Graph States
- Improving zero-error classical communication with entanglement
- Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
- On the Classification of All Self-Dual Additive Codes over GF(4) of Length up to 12
- Experimental fully contextual correlations
- Mermin inequalities for perfect correlations
- Entanglement in eight-qubit graph states
- A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity
- Experimental observation of impossible-to-beat quantum advantage on a hybrid photonic system
- Violating the Shannon capacity of metric graphs with entanglement
- On Local Equivalence, Surface Code States and Matroids