On the quantum chromatic number of a graph
From MaRDI portal
Publication:1010645
zbMath1182.05054arXivquant-ph/0608016MaRDI QIDQ1010645
Andreas Winter, Simone Severini, Ashley Montanaro, Michael W. Newman, Peter J. Cameron
Publication date: 7 April 2009
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0608016
Random graphs (graph-theoretic aspects) (05C80) Quantum computation (81P68) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Network protocols (68M12)
Related Items
Conic formulations of graph homomorphisms ⋮ Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone ⋮ Quantum Bilinear Optimization ⋮ Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization ⋮ Belief-invariant and quantum equilibria in games of incomplete information ⋮ Sabidussi versus Hedetniemi for three variations of the chromatic number ⋮ Deterministic quantum non-locality and graph colorings ⋮ Classical, quantum and nonsignalling resources in bipartite games ⋮ Maximally Entangled State in Pseudo-Telepathy Games ⋮ A compositional approach to quantum functions ⋮ New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix ⋮ Quantum and non-signalling graph isomorphisms ⋮ Properties of operator systems, corresponding to channels ⋮ \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem ⋮ Discrete quantum structures. II: Examples ⋮ Unnamed Item ⋮ \(\mathrm{C}^\ast\)-algebras. Abstracts from the workshop held August 7--13, 2022 ⋮ Approximating projections by quantum operations ⋮ Spectral bounds for the quantum chromatic number of quantum graphs ⋮ Quantum hypergraph homomorphisms and non-local games ⋮ Discrete quantum structures. I: Quantum predicate logic ⋮ Unnamed Item ⋮ Spectral lower bounds for the quantum chromatic number of a graph. II ⋮ Quantum sets ⋮ Quantum multiplicative graph and a type of separate clique number ⋮ Quantum privacy and Schur product channels ⋮ Linear conic formulations for two-party correlations and values of nonlocal games ⋮ Spectral upper bound on the quantum k-independence number of a graph ⋮ Synchronous correlation matrices and Connes’ embedding conjecture ⋮ Unnamed Item ⋮ Estimating quantum chromatic numbers ⋮ Unnamed Item ⋮ Quantum extensions of ordinary maps ⋮ 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 homomorphisms
