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