Abstract: 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.
Recommendations
- Spectral bounds for the quantum chromatic number of quantum graphs
- Spectral lower bounds for the quantum chromatic number of a graph
- On the chromatic number of \(q\)-Kneser graphs
- Estimating quantum chromatic numbers
- Quantum approaches to graph colouring
- On the chromatic number of graphs
- Spectral lower bounds for the quantum chromatic number of a graph. II
- Quantum chromatic numbers via operator systems
- On the chromatic dimension of a graph
- scientific article; zbMATH DE number 77956
Cited in
(57)- Quantum approaches to graph colouring
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Sabidussi versus Hedetniemi for three variations of the chromatic number
- Algebras, synchronous games, and chromatic numbers of graphs
- Quantum privacy and Schur product channels
- Spectral lower bounds for the quantum chromatic number of a graph. II
- Connectivity for quantum graphs
- Perfect strategies for non-local games
- Topological bounds on the dimension of orthogonal representations of graphs
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- Spectral lower bounds for the quantum chromatic number of a graph
- Quantum and non-signalling graph isomorphisms
- Quantum homomorphisms
- Belief-invariant and quantum equilibria in games of incomplete information
- Properties of operator systems, corresponding to channels
- Approximating projections by quantum operations
- Synchronous correlation matrices and Connes' embedding conjecture
- Maximally Entangled State in Pseudo-Telepathy Games
- Conic formulations of graph homomorphisms
- Graph homomorphisms for quantum players
- Quantum bilinear optimization
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Deterministic quantum non-locality and graph colorings
- Classical, quantum and nonsignalling resources in bipartite games
- New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
- A compositional approach to quantum functions
- scientific article; zbMATH DE number 7453174 (Why is no real title available?)
- Approximating the orthogonality dimension of graphs and hypergraphs
- Spectral upper bound on the quantum \(k\)-independence number of a graph
- The quantum monad on relational structures
- Quantum sets
- Quantum multiplicative graph and a type of separate clique number
- Linear conic formulations for two-party correlations and values of nonlocal games
- Quantum extensions of ordinary maps
- Quantum chromatic numbers via operator systems
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- scientific article; zbMATH DE number 6744339 (Why is no real title available?)
- Approximating the orthogonality dimension of graphs and hypergraphs
- Estimating quantum chromatic numbers
- \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
- Discrete quantum structures. II: Examples
- \(\mathrm{C}^\ast\)-algebras. Abstracts from the workshop held August 7--13, 2022
- Spectral bounds for the quantum chromatic number of quantum graphs
- Quantum hypergraph homomorphisms and non-local games
- Discrete quantum structures. I: Quantum predicate logic
- Quantum no-signalling correlations and non-local games
- Semi-definite programming and quantum information
- Homomorphisms of quantum hypergraphs
- Quantum Mycielski graphs
- Kernelization for orthogonality dimension
- Quantum advantage and CSP complexity
- A spectral lower bound on chromatic numbers using p-energy
- Quantum chromatic number of products of quantum graphs
- Quantum advantage and CSP complexity
- Satisfiability problems and algebras of Boolean constraint system games
- On the quantum chromatic numbers of small graphs
- Kernelization for orthogonality dimension
This page was built for publication: On the quantum chromatic number of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010645)
