KAIST Discrete Math Seminar

I 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 Lovasz 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 quantum graph state associated with G, and exclusive events are adjacent. 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. The construction also describes a pseudo-telepathy game which is always won when using quantum resources but not always using classical resources. Finally we generalise the graph state to the mixed graph state and discuss how the previous construction may, therefore, be generalized. Joint work with: Cabello, Scarpa, Severini, Riera, Rahaman.