2005/09/07 by Chris Godsil, C. D. Godsil, Michael Newman +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.math/0509151
13 pages
arxiv created 2005/09/07 · openalex publication_date 2005/09/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We deal with a graph colouring problem that arises in quantum information theory. Alice and Bob are each given a ±1-vector of length k, and are to respond with k bits. Their responses must be equal if they are given equal inputs, and distinct if they are given orthogonal inputs; however, they are not allowed to communicate any information about their inputs. They can always succeed using quantum entanglement, but their ability to succeed using only classical physics is equivalent to a graph colouring problem. We resolve the graph colouring problem, thus determining that they can succeed without entanglement exactly when k≤3.