Oddities of Quantum Colorings

Laura Mancinska, David E. Roberson

Research output: Contribution to journalArticle (Academic Journal)peer-review

271 Downloads (Pure)


The main purpose of this work is to collect some interesting facts related to quantum graph coloring. We consider the orthogonality graph of the three-dimensional vectors with entries from the set {-1, 0, 1}. If we ignore the overall sign of the vectors, this yields a graph on thirteen vertices, which we denote by G13. It turns out that G13 (or the graph obtained from this by adding an apex vertex) is the smallest known example which exhibits separations between several graph parameters. We are particularly interested in using G13 to separate quantum graph parameters from their classical counterparts. We give a proof that G13 is not quantum 3-colorable, which shows that its orthogonal rank is strictly less than its quantum chromatic number. This also proves, along with other previously known results, that adding an apex vertex to G13 does not change its quantum chromatic number. The graph G13 is the first and only known graph with either of these properties. Lastly, we investigate a graph construction used for taking instances of 3-SAT to instances of 3-COLORING. We show that any graph constructed in this manner has an orthogonal representation in dimension three if and only if it is 3-colorable. Since it has been previously shown that there are such graphs with quantum 3-colorings but no classical 3-colorings, it follows that quantum chromatic number can be strictly less than orthogonal rank. Together with the above, this proves that orthogonal rank and quantum chromatic number are not comparable as graph parameters.
Original languageEnglish
Pages (from-to)846–859
Number of pages14
JournalBaltic Journal on Modern Computing
Issue number4
Early online date22 Dec 2016
Publication statusPublished - Dec 2016


  • quantum chromatic number
  • entanglement
  • orthogonal rank
  • nonlocal games


Dive into the research topics of 'Oddities of Quantum Colorings'. Together they form a unique fingerprint.

Cite this