Colouring an Orthogonality Graph
| dc.creator | Godsil, C. D. | |
| dc.creator | Newman, M. W. | |
| dc.date | 2005-09-07 | |
| dc.date.accessioned | 2026-07-07T05:23:00Z | |
| dc.date.available | 2026-07-07T05:23:00Z | |
| dc.description | We deal with a graph colouring problem that arises in quantum information theory. Alice and Bob are each given a $\pm1$-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\leq3$. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/math/0509151 | |
| dc.identifier | http://arxiv.org/abs/math/0509151 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/76277 | |
| dc.subject | Combinatorics | |
| dc.title | Colouring an Orthogonality Graph | |
| dc.type | text |