The determination of the quantum chromatic number of graphs has attracted considerable attention recently. However, there are few families of graphs whose quantum chromatic numbers are determined. A notable exception is the family of orthogonality graphs, whose quantum chromatic numbers are fully determined. In this paper, we extend these results by determining the exact quantum chromatic number of several subgraphs of the orthogonality graphs. Using the technique of combinatorial designs, we also determine the quantum chromatic number of the distance-2 Hamming graph, whose edges consist of binary vectors of Hamming distance 2, for infinitely many length.
The study of quantum chromatic numbers of graphs is a hot research topic in recent years. However, the infinite family of graphs with known quantum chromatic numbers are rare, as far as we know, the only known such graphs (except for complete graphs, cycles, bipartite graphs and some trivial cases) are the Hadamard graphs
Hn with
2n vertices and
n a multiple of
4. In this paper, we consider the graphs in Hamming schemes, we determined the quantum chromatic numbers of one class of such graphs. Notably, this is the second known family of graphs whose quantum chromatic numbers are explicitly determined except for some cases aforementioned. We also provide some bounds for the quantum chromatic numbers of some other graphs in Hamming schemes. Consequently, we can obtain the quantum chromatic numbers of products of some graphs.
The quantum chromatic number is a fundamental parameter in the study of nonlocal games, capturing the extent to which entanglement can improve performance in distributed tasks. In this paper, we investigate the quantum chromatic number of generalized Johnson graphs. By constructing modulus-one orthogonal representations, we obtain general upper bounds on their quantum chromatic numbers. We further analyze the smallest eigenvalue of these graphs. Combining the resulting Hoffman-type lower bounds with the upper bounds obtained from orthogonal representations, we determine the exact quantum chromatic numbers of two infinite families of generalized Johnson graphs. Finally, applying a forbidden-distance theorem for binary codes, we show that the classical chromatic numbers of these families grow exponentially with
n, whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.
We investigate the notion of quantum chromatic number of a graph, which is the minimal number of colours necessary in a protocol in which two separated provers can convince a referee that they have a colouring of the graph.After discussing this notion from first principles, we go on to establish relations with the clique number and orthogonal representations of the graph. We also prove several general facts about this graph parameter and find large separations between the clique number and the quantum chromatic number by looking at random graphs. Finally, we show that there can be no separation between classical and quantum chromatic number if the latter is
2, nor if it is
3 in a restricted quantum model; on the other hand, we exhibit a graph on
18 vertices and
44 edges with chromatic number
5 and quantum chromatic number
4.
The quantum chromatic number of a graph G is sandwiched between its chromatic number and its clique number, which are well-known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number χq(1)(G), which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number χ(G) and the minimum dimension of orthogonal representations ξ(G). It is known that ξ(G) ≤ χq(1)(G) ≤ χ(G). We answer three open questions about these relations: we give a necessary and sufficient condition to have ξ(G) = χq(1)(G), we exhibit a class of graphs such that ξ(G) ≤ χq(1)(G), and we give a necessary and sufficient condition to have χq(1)(G) ≤ χ(G). Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of contextuality of physical theories and, more recently, in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis et al on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.
The quantum chromatic number of a graph
G is sandwiched between its chromatic number and its clique number, which are well known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number
χq(1)(G), which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number
χ(G) and the minimum dimension of orthogonal representations
ξ(G). It is known that
ξ(G)≤χq(1)(G)≤χ(G). We answer three open questions about these relations: we give a necessary and sufficient condition to have
ξ(G)=χq(1)(G), we exhibit a class of graphs such that
ξ(G)<χq(1)(G), and we give a necessary and sufficient condition to have
χq(1)(G)<χ(G). Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of noncontextuality of physical theories, and more recently in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis, Hasegawa, Kikuchi, and Sasaki on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.
We make two contributions pertaining to the study of the quantum chromatic numbers of small graphs. Firstly, in an elegant paper, Mančinska and Roberson [Baltic Journal on Modern Computing, 4(4), 846-859, 2016] gave an example of a graph
G14 on 14 vertices with quantum chromatic number 4 and classical chromatic number 5, and conjectured that this is the smallest graph exhibiting a separation between the two parameters. We describe a computer-assisted proof of this conjecture, thereby resolving a longstanding open problem in quantum graph theory. Our second contribution pertains to the study of the rank-
r quantum chromatic numbers. While it can now be shown that for every
r,
χq and
χq(r) are distinct, few small examples of separations between these parameters are known. We give the smallest known example of such a separation in the form of a graph
G21 on 21 vertices with
χq(G21)=χq(2)(G21)=4 and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph
Gmsg on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies
χq(Gmsg)=3 and
χq(1)(Gmsg)=4. In addition,
G21 provides the first provable separation between the parameters
χq(1) and
χq(2). We believe that our techniques for constructing
G21 and lower bounding its orthogonal rank could be of independent interest.