Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

SIAM Journal on Discrete Mathematics

Coloring an Orthogonality Graph

Chris D. Godsil, M. W. Newman

Published Jan 1, 2008• 26 citations
Publisher

Abstract

We deal with a graph coloring problem that arises in quantum information theory. Alice and Bob are each given a $\pm1$-vector of length $2^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 coloring problem. We resolve the graph coloring problem, thus determining that they can succeed without entanglement exactly when $k\leq3$.

DOI
10.1137/050639715

Related papers

Colouring an Orthogonality Graph

Chris D. Godsil, Newman, M. W.

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$.

arXiv:math/0509151•Sep 7, 2005•5 citations

On the orthogonal rank and impossibility of quantum round elimination

Jop Briët, Jeroen Zuiddam

After Bob sends Alice a bit, she responds with a lengthy reply. At the cost of a factor of two in the total communication, Alice could just as well have given Bob her two possible replies at once without listening to him at all, and have him select which one applies. Motivated by a conjecture stating that this form of “round elimination” is impossible in exact quantum communication complexity, we study the orthogonal rank and a symmetric variant thereof for a certain family of Cayley graphs. The orthogonal rank of a graph is the smallest number d for which one can label each vertex with a nonzero d-dimensional complex vector such that adjacent vertices receive orthogonal vectors. We show an exp(n) lower bound on the orthogonal rank of the graph on {0, 1} n in which two strings are adjacent if they have Hamming distance at least n/2. In combination with previous work, this implies an affirmative answer to the above conjecture.

Quantum Information and Computation•Jan 1, 2017•4 citations

On the orthogonal rank of Cayley graphs and impossibility of quantum round elimination

Jop Briët, Jeroen Zuiddam

After Bob sends Alice a bit, she responds with a lengthy reply. At the cost of a factor of two in the total communication, Alice could just as well have given the two possible replies without listening and have Bob select which applies to him. Motivated by a conjecture stating that this form of "round elimination" is impossible in exact quantum communication complexity, we study the orthogonal rank and a symmetric variant thereof for a certain family of Cayley graphs. The orthogonal rank of a graph is the smallest number $d$ for which one can label each vertex with a nonzero $d$-dimensional complex vector such that adjacent vertices receive orthogonal vectors. We show an exp$(n)$ lower bound on the orthogonal rank of the graph on $\{0,1\}^n$ in which two strings are adjacent if they have Hamming distance at least $n/2$. In combination with previous work, this implies an affirmative answer to the above conjecture.

arXiv:1608.06113•Aug 22, 2016•5 citations

Oddities of Quantum Colorings

Laura Mančinska, David E. Roberson

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.

arXiv:1801.03542•Baltic Journal of Modern Computing•Dec 19, 2016•2 citations

Perfect Games in Dimension-Bounded Communication

Emmanuel Zambrini Cruzeiro

Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension $d$ satisfies every prescribed winning constraint, whereas a classical $d$-level message cannot. We establish three structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a $d$-level message is equivalent to $d$-colorability, perfect $d$-dimensional quantum realization is equivalent to a $d$-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. Third, with at most two Bob inputs every perfect qutrit strategy admits a perfect classical-trit realization. An explicit seven-preparation qutrit game with three Bob inputs satisfies $C_3=20<Q_3=S=21$, so three Bob inputs are necessary and sufficient in dimension three. Conversely, a two-input, six-output game in dimension five satisfies $C_5=39<Q_5=S=40$. Thus the smallest dimension admitting a two-input perfect same-dimensional separation is either four or five; the four-dimensional case remains open. As a flagship binary application, the $13$-ray qutrit graph yields a compressed game $(X,Y,B)=(13,8,2)$ with $C_3=39<Q_3=S=40$, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.

quant-pharXiv:2608.05092•Aug 6, 2026•0 citations

χ-colorable graph states: closed-form expressions and quantum orthogonal arrays

Konstantinos-Rafail Revis, Hrachya Zakaryan, Zahra Raissi

Abstract Graph states are a fundamental class of multipartite entangled quantum states with wide-ranging applications in quantum information and computation. In this work, we develop a systematic approach for constructing and analyzing χ-colorable graph states, deriving explicit closed-form expressions for arbitrary χ. For a broad family of two- and three-colorable graph states, the representations obtained using only local operations require a minimal number of terms in the Z-eigenbasis. We prove that every two-colorable graph state is local Clifford (LC) equivalent to a state expressible as a summation of rows of an orthogonal array (OA). For graph states with χ > 2, we show that they are LC-equivalent to quantum OAs, establishing a direct combinatorial connection between multipartite entanglement and structured quantum states. Furthermore, the upper and lower bounds of the Schmidt measure for graph states with arbitrary χ colorability are discussed, extending the results for an arbitrary local dimension. Our results offer an efficient and practical method for systematically constructing graph states, optimizing their representation in quantum circuits, and identifying structured forms of multipartite entanglement. This approach also connects graph states to k-uniform and absolutely maximally entangled states, motivating further exploration of the structure of entangled states and their applications in quantum networks, quantum error correction, and measurement based quantum computing.

arXiv:2408.09515•Journal of Physics A Mathematical and Theoretical•Aug 21, 2025•0 citations
We deal with a graph coloring problem that arises in quantum information theory. Alice and Bob are each given a ±1\pm1±1-vector of length 2k2^k2k 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 coloring problem. We resolve the graph coloring problem, thus determining that they can succeed without entanglement exactly when k≤3k\leq3k≤3.
We deal with a graph colouring problem that arises in quantum information theory. Alice and Bob are each given a ±1\pm1±1-vector of length kkk, and are to respond with kkk 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≤3k\leq3k≤3.
After Bob sends Alice a bit, she responds with a lengthy reply. At the cost of a factor of two in the total communication, Alice could just as well have given Bob her two possible replies at once without listening to him at all, and have him select which one applies. Motivated by a conjecture stating that this form of “round elimination” is impossible in exact quantum communication complexity, we study the orthogonal rank and a symmetric variant thereof for a certain family of Cayley graphs. The orthogonal rank of a graph is the smallest number d for which one can label each vertex with a nonzero d-dimensional complex vector such that adjacent vertices receive orthogonal vectors. We show an exp(n) lower bound on the orthogonal rank of the graph on {0, 1} n in which two strings are adjacent if they have Hamming distance at least n/2. In combination with previous work, this implies an affirmative answer to the above conjecture.
After Bob sends Alice a bit, she responds with a lengthy reply. At the cost of a factor of two in the total communication, Alice could just as well have given the two possible replies without listening and have Bob select which applies to him. Motivated by a conjecture stating that this form of "round elimination" is impossible in exact quantum communication complexity, we study the orthogonal rank and a symmetric variant thereof for a certain family of Cayley graphs. The orthogonal rank of a graph is the smallest number ddd for which one can label each vertex with a nonzero ddd-dimensional complex vector such that adjacent vertices receive orthogonal vectors. We show an exp(n)(n)(n) lower bound on the orthogonal rank of the graph on {0,1}n\{0,1\}^n{0,1}n in which two strings are adjacent if they have Hamming distance at least n/2n/2n/2. In combination with previous work, this implies an affirmative answer to the above conjecture.
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.
Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension ddd satisfies every prescribed winning constraint, whereas a classical ddd-level message cannot. We establish three structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a ddd-level message is equivalent to ddd-colorability, perfect ddd-dimensional quantum realization is equivalent to a ddd-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. Third, with at most two Bob inputs every perfect qutrit strategy admits a perfect classical-trit realization. An explicit seven-preparation qutrit game with three Bob inputs satisfies C3=20<Q3=S=21C_3=20<Q_3=S=21C3​=20<Q3​=S=21, so three Bob inputs are necessary and sufficient in dimension three. Conversely, a two-input, six-output game in dimension five satisfies C5=39<Q5=S=40C_5=39<Q_5=S=40C5​=39<Q5​=S=40. Thus the smallest dimension admitting a two-input perfect same-dimensional separation is either four or five; the four-dimensional case remains open. As a flagship binary application, the 131313-ray qutrit graph yields a compressed game (X,Y,B)=(13,8,2)(X,Y,B)=(13,8,2)(X,Y,B)=(13,8,2) with C3=39<Q3=S=40C_3=39<Q_3=S=40C3​=39<Q3​=S=40, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.
Abstract Graph states are a fundamental class of multipartite entangled quantum states with wide-ranging applications in quantum information and computation. In this work, we develop a systematic approach for constructing and analyzing χ-colorable graph states, deriving explicit closed-form expressions for arbitrary χ. For a broad family of two- and three-colorable graph states, the representations obtained using only local operations require a minimal number of terms in the Z-eigenbasis. We prove that every two-colorable graph state is local Clifford (LC) equivalent to a state expressible as a summation of rows of an orthogonal array (OA). For graph states with χ > 2, we show that they are LC-equivalent to quantum OAs, establishing a direct combinatorial connection between multipartite entanglement and structured quantum states. Furthermore, the upper and lower bounds of the Schmidt measure for graph states with arbitrary χ colorability are discussed, extending the results for an arbitrary local dimension. Our results offer an efficient and practical method for systematically constructing graph states, optimizing their representation in quantum circuits, and identifying structured forms of multipartite entanglement. This approach also connects graph states to k-uniform and absolutely maximally entangled states, motivating further exploration of the structure of entangled states and their applications in quantum networks, quantum error correction, and measurement based quantum computing.