On the quantum chromatic number of a graph
From MaRDI portal
Publication:1010645
zbMATH Open1182.05054arXivquant-ph/0608016MaRDI QIDQ1010645FDOQ1010645
Authors: Ashley Montanaro, Mike Newman, Simone Severini, Andreas Winter, Peter J. Cameron 
Publication date: 7 April 2009
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/quant-ph/0608016
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
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
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Quantum computation (81P68) Coloring of graphs and hypergraphs (05C15) Network protocols (68M12)
Cited In (48)
- Quantum homomorphisms
- Conic formulations of graph homomorphisms
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Semi-definite programming and quantum information
- Title not available (Why is that?)
- Algebras, synchronous games, and chromatic numbers of graphs
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- Quantum and non-signalling graph isomorphisms
- Connectivity for quantum graphs
- 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
- Title not available (Why is that?)
- Quantum chromatic numbers via operator systems
- Title not available (Why is that?)
- Discrete quantum structures. I: Quantum predicate logic
- Sabidussi versus Hedetniemi for three variations of the chromatic number
- Homomorphisms of quantum hypergraphs
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Graph homomorphisms for quantum players
- Properties of operator systems, corresponding to channels
- Spectral upper bound on the quantum \(k\)-independence number of a graph
- Spectral lower bounds for the quantum chromatic number of a graph. II
- 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
- Title not available (Why is that?)
- 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
- \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
- Discrete quantum structures. II: Examples
- Deterministic quantum non-locality and graph colorings
- Quantum sets
- Perfect strategies for non-local games
- Quantum no-signalling correlations and non-local games
- Estimating quantum chromatic numbers
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)
