arXiv:1805.08334

Spectral lower bounds for the quantum chromatic number of a graph

Paweł Wocjan, Clive H. Elphick

Published May 22, 2018• 1 citation

Abstract

The quantum chromatic number, $χ_q(G)$, of a graph $G$ was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot communicate with each other but share an entangled state can convince an interrogator with certainty that they have a coloring of the graph. We use an equivalent purely combinatorial definition of $χ_q(G)$ to prove that many spectral lower bounds for the chromatic number, $χ(G)$, are also lower bounds for $χ_q(G)$. This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.

DOI: 10.48550/arxiv.1805.08334

Related papers

On the quantum chromatic number of a graph

Peter J‎. Cameron, Ashley Montanaro, Michael Newman +2 more

arXiv:quant-ph/0608016Aug 1, 20063 citations

On the Quantum Chromatic Number of a Graph

Peter J‎. Cameron, Ashley Montanaro, Michael Newman +2 more

The Electronic Journal of CombinatoricsNov 28, 2007100 citations

A counterexample to the quantum Hedetniemi conjecture

Julius A. Zeiss

math.COCross-listedarXiv:2609.20690Sep 18, 20260 citations

On the Quantum Chromatic Numbers of Small Graphs

Olivier Lalonde

arXiv:2311.08194The Electronic Journal of CombinatoricsFeb 14, 20251 citation

On the exact quantum chromatic number of generalized Johnson graphs

Gaojun Luo, Xiwang Cao, Shitao Li +1 more

arXiv:2609.04677Sep 4, 20260 citations

1 Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number

Giannicola Scarpa, Simone Severini B

Apr 1, 201225 citations

arXiv:1805.08334

Spectral lower bounds for the quantum chromatic number of a graph

Paweł Wocjan, Clive H. Elphick

Published May 22, 2018• 1 citation

arXiv HTML PDF

Abstract

The quantum chromatic number,

χ_q(G)

, of a graph

G

was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot communicate with each other but share an entangled state can convince an interrogator with certainty that they have a coloring of the graph. We use an equivalent purely combinatorial definition of

χ_q(G)

to prove that many spectral lower bounds for the chromatic number,

χ(G)

, are also lower bounds for

χ_q(G)

. This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.

DOI: 10.48550/arxiv.1805.08334

Related papers

On the quantum chromatic number of a graph

Peter J‎. Cameron, Ashley Montanaro, Michael Newman +2 more

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 an interrogator with certainty 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.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 an interrogator with certainty 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.

arXiv:quant-ph/0608016Aug 1, 20063 citations

On the Quantum Chromatic Number of a Graph

Peter J‎. Cameron, Ashley Montanaro, Michael Newman +2 more

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$ .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 Electronic Journal of CombinatoricsNov 28, 2007100 citations

A counterexample to the quantum Hedetniemi conjecture

Julius A. Zeiss

Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs $G,H$ with $χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).$ The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital $C^*$ -algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and $C^*$ -algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs $G,H$ with \[ χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).\]The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital $C^*$-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and $C^*$-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.

math.COCross-listedarXiv:2609.20690Sep 18, 20260 citations

On the Quantum Chromatic Numbers of Small Graphs

Olivier Lalonde

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 $G_{14}$ 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$ , $\chi_q$ and $\chi^{(r)}_q$ 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 $G_{21}$ on 21 vertices with $\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4$ and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph $G_{msg}$ on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies $\chi_q(G_{msg}) = 3$ and $\chi^{(1)}_q(G_{msg}) = 4$ . In addition, $G_{21}$ provides the first provable separation between the parameters $\chi^{(1)}_q$ and $\chi^{(2)}_q$ . We believe that our techniques for constructing $G_{21}$ and lower bounding its orthogonal rank could be of independent interest.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 $G_{14}$ 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$, $\chi_q$ and $\chi^{(r)}_q$ 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 $G_{21}$ on 21 vertices with $\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4$ and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph $G_{msg}$ on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies $\chi_q(G_{msg}) = 3$ and $\chi^{(1)}_q(G_{msg}) = 4$. In addition, $G_{21}$ provides the first provable separation between the parameters $\chi^{(1)}_q$ and $\chi^{(2)}_q$. We believe that our techniques for constructing $G_{21}$ and lower bounding its orthogonal rank could be of independent interest.

arXiv:2311.08194The Electronic Journal of CombinatoricsFeb 14, 20251 citation

On the exact quantum chromatic number of generalized Johnson graphs

Gaojun Luo, Xiwang Cao, Shitao Li +1 more

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

arXiv:2609.04677Sep 4, 20260 citations

1 Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number

Giannicola Scarpa, Simone Severini B

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 $\chi_q^{(1)}(G)$ , which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number $\chi(G)$ and the minimum dimension of orthogonal representations $\xi(G)$ . It is known that $\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)$ . We answer three open questions about these relations: we give a necessary and sufficient condition to have $\xi(G) = \chi_q^{(1)}(G)$ , we exhibit a class of graphs such that $\xi(G) < \chi_q^{(1)}(G)$ , and we give a necessary and sufficient condition to have $\chi_q^{(1)}(G) < \chi(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.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 $\chi_q^{(1)}(G)$, which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number $\chi(G)$ and the minimum dimension of orthogonal representations $\xi(G)$. It is known that $\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)$. We answer three open questions about these relations: we give a necessary and sufficient condition to have $\xi(G) = \chi_q^{(1)}(G)$, we exhibit a class of graphs such that $\xi(G) < \chi_q^{(1)}(G)$, and we give a necessary and sufficient condition to have $\chi_q^{(1)}(G) < \chi(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.

Apr 1, 201225 citations

The quantum chromatic number,

χ_q(G)

, of a graph

G

χ_q(G)

to prove that many spectral lower bounds for the chromatic number,

χ(G)

, are also lower bounds for

χ_q(G)

. This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.

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

G,H

with

χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).

The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital

C^*

-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and

C^*

-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.

G_{14}

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

\chi_q

and

\chi^{(r)}_q

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

G_{21}

on 21 vertices with

\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4

and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph

G_{msg}

on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies

\chi_q(G_{msg}) = 3

and

\chi^{(1)}_q(G_{msg}) = 4

. In addition,

G_{21}

provides the first provable separation between the parameters

\chi^{(1)}_q

and

\chi^{(2)}_q

. We believe that our techniques for constructing

G_{21}

and lower bounding its orthogonal rank could be of independent interest.

n

, whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.

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

\chi_q^{(1)}(G)

, which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number

\chi(G)

and the minimum dimension of orthogonal representations

\xi(G)

. It is known that

\xi(G) \leq \chi_q^{(1)}(G) \leq \chi(G)

. We answer three open questions about these relations: we give a necessary and sufficient condition to have

\xi(G) = \chi_q^{(1)}(G)

, we exhibit a class of graphs such that

\xi(G) < \chi_q^{(1)}(G)

, and we give a necessary and sufficient condition to have

\chi_q^{(1)}(G) < \chi(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.