Projects per year

## Abstract

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

*G*_{13}. It turns out that*G*_{13}(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*G*_{13}to separate quantum graph parameters from their classical counterparts. We give a proof that*G*_{13}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*G*_{13}does not change its quantum chromatic number. The graph*G*_{13}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 language | English |
---|---|

Pages (from-to) | 846–859 |

Number of pages | 14 |

Journal | Baltic Journal on Modern Computing |

Volume | 4 |

Issue number | 4 |

Early online date | 22 Dec 2016 |

DOIs | |

Publication status | Published - Dec 2016 |

## Keywords

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

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

## Projects

- 2 Finished