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