QLunch: Oddities of Quantum colorings

Speaker: Laura Mančinska from QMATH

Title: Oddities of Quantum colorings

Abstract:
We consider entanglement-assisted strategies for an interactive proof system in which two separated provers aim to convince a verifier that a given graph G admits a c-coloring. We refer to such strategies as quantum c-colorings of G. Along with the related notion of quantum chromatic number, \chi_q(G), they have been investigated in series of prior works. Here we exhibit several unexpected behaviors of quantum colorings and chromatic number. For instance, we show that unlike the classical chromatic number, \chi(G), the quantum chromatic number does not necessarily increase if we extend graph G by adding an additional vertex which is adjacent to all vertices of G. 

Almost all previously known separations between quantum and classical chromatic number originate from separations between classical chromatic number and orthogonal rank, \xi(G). We show the limitations of this method by establishing that quantum chromatic number and orthogonal rank are in fact incomparable. In particular, we exhibit two graphs G and H such that \chi_q(G)>\xi(G) and \chi_q(H)<\xi(H). The graph G is obtained from the orthogonality graph of all the three-dimensional vectors with entries from the set {-1,0,1} by identifying the vectors that only differ by an overall sign. It turns out that a small modification to G also yields the smallest known graph, G', with \chi_q(G') < \chi(G'). Finally, for constructing graph H with \chi_q(H)<\xi(H) we use classical reductions of 3-SAT decision problem to 3-COLORING.

This talk is a based on arXiv:1801.03542