Quantum Chromatic Number
The quantum chromatic number chi_q(G) of a graph G is a quantum analog of the chromatic number. It is the minimum number k of colors for which two separated players can win the k-coloring game on G with certainty using an entangled strategy. In this game, the players are given vertices x and y of G which are promised to be equal or adjacent. They must return colors that agree when x=y and differ when x and y are adjacent (Cameron et al. 2007).
Classical deterministic strategies for the coloring game are equivalent to ordinary vertex colorings, and therefore
| chi_q(G)<=chi(G). |
(1)
|
Quantum 2-colorability is exactly the property of being bipartite. Thus a non-bipartite graph satisfies chi_q(G)>=3, and hence chi_q(G)=3 whenever chi(G)=3.
The inequality can be strict. Mančinska and Roberson (2016) considered a 13-vertex Mančinska-Roberson graph G_(13) that is the orthogonality graph of the nonzero vectors in {-1,0,1}^3 modulo overall sign. This graph is also the Yu-Oh 13-ray graph used in state-independent Kochen-Specker contextuality (Yu and Oh 2012, Cabello et al. 2016). Adding an apex vertex to G_(13) gives a 14-vertex Mančinska-Roberson graph G_(14) with chi_q(G_(14))=4 and chi(G_(14))=5 (Mančinska and Roberson 2016). Cameron et al. (2007) previously gave the 18-vertex Cameron-Montanaro-Newman-Severini-Winter graph G_(18) with the same separation. Lalonde (2025) proved that G_(14) is the smallest possible separation between chi_q and chi, measured by number of vertices, and in particular that chi_q(G)=chi(G) for every graph G with at most 13 vertices, and also for 14-vertex graphs with chi(G)<=4.
There are also variants such as the approximate and commuting quantum chromatic numbers, usually denoted chi_(qa) and chi_(qc), for which
| chi_(qc)(G)<=chi_(qa)(G)<=chi_q(G)<=chi(G) |
(2)
|
(Paulsen and Todorov 2015, Lalonde 2025).
Algorithmically, Paulsen et al. (2016) described a semidefinite programming hierarchy converging to chi_(qc), while Gribling et al. (2018) placed quantum graph parameters in a tracial noncommutative polynomial optimization framework, i.e., one based on traces of polynomial expressions in noncommuting operator variables, and gave Lasserre-type semidefinite programming hierarchies converging to the commuting quantum chromatic number. For small graphs, Lalonde (2025) also used a recursive obstruction method for proving nonexistence of low-dimensional orthogonal representations in cases where semidefinite programming bounds alone were insufficient.
The rank-r quantum chromatic number chi_q^((r))(G) further requires all measurement projectors in a quantum coloring to have rank exactly r. Lalonde (2025) gave the 21-vertex Lalonde graph G_(21) with
| chi_q(G_(21))=chi_q^((2))(G_(21))=4 |
(3)
|
and
| xi(G_(21))=chi_q^((1))(G_(21))=chi(G_(21))=5, |
(4)
|
where xi denotes orthogonal rank. This graph is illustrated above in a number of bilaterally symmetric embeddings and gives the first provable separation between the rank-1 and rank-2 quantum chromatic numbers.
See also
Cameron-Montanaro-Newman-Severini-Winter Graph, Chromatic Number, Graph Coloring, Lalonde Graph, Mancinska-Roberson Graphs, Vertex ColoringExplore with Wolfram|Alpha
More things to try:
References
Cabello, A.; Kleinmann, M.; and Portillo, J. R. "Quantum State-Independent Contextuality Requires 13 Rays." J. Phys. A: Math. Theor. 49, 38LT01, 2016. https://doi.org/10.1088/1751-8113/49/38/38LT01.Cameron, P. J.; Montanaro, A.; Newman, M. W.; Severini, S.; and Winter, A. "On the Quantum Chromatic Number of a Graph." Elec. J. Combin. 14, No. 1, R81, 2007. https://doi.org/10.37236/999.Gribling, S.; de Laat, D.; and Laurent, M. "Bounds on Entanglement Dimensions and Quantum Graph Parameters via Noncommutative Polynomial Optimization." Math. Programming 170, 5-42, 2018. https://doi.org/10.1007/s10107-018-1287-z.House of Graphs. "Orthogonality Graph of Magic Cube." https://houseofgraphs.org/graphs/18432.Lalonde, O. "On the Quantum Chromatic Numbers of Small Graphs." Elec. J. Combin. 32, No. 1, P1.18, 1-26, 2025. https://doi.org/10.37236/12506.Mančinska, L. and Roberson, D. E. "Oddities of Quantum Colorings." Baltic J. Modern Computing 4, 846-859, 2016. https://doi.org/10.22364/bjmc.2016年4月4日.16.Paulsen, V. I.; Severini, S.; Stahlke, D.; Todorov, I. G.; and Winter, A. "Estimating Quantum Chromatic Numbers." J. Funct. Anal. 270, 2188-2222, 2016. https://doi.org/10.1016/j.jfa.2016年01月01日0.Paulsen, V. I. and Todorov, I. G. "Quantum Chromatic Numbers via Operator Systems." Quart. J. Math. 66, 677-692, 2015. https://doi.org/10.1093/qmath/hav004.Yu, S. and Oh, C. H. "State-Independent Proof of Kochen-Specker Theorem with 13 Rays." Phys. Rev. Lett. 108, 030402, 2012. https://doi.org/10.1103/PhysRevLett.108.030402.Cite this as:
Weisstein, Eric W. "Quantum Chromatic Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/QuantumChromaticNumber.html