Estimating quantum chromatic numbers
arXiv:1407.6918 · doi:10.1016/j.jfa.2016.01.010
Abstract
We develop further the new versions of quantum chromatic numbers of graphs introduced by the first and fourth authors. We prove that the problem of computation of the commuting quantum chromatic number of a graph is solvable by an SDP algorithm and describe an hierarchy of variants of the commuting quantum chromatic number which converge to it. We introduce the tracial rank of a graph, a parameter that gives a lower bound for the commuting quantum chromatic number and parallels the projective rank, and prove that it is multiplicative. We describe the tracial rank, the projective rank and the fractional chromatic numbers in a unified manner that clarifies their connection with the commuting quantum chromatic number, the quantum chromatic number and the classical chromatic number, respectively. Finally, we present a new SDP algorithm that yields a parameter larger than the Lovász number and is yet a lower bound for the tracial rank of the graph. We determine the precise value of the tracial rank of an odd cycle.
34 pages; v2 has improved presentation based after referees' comments, published version
References in corpus (4)
Cited by in corpus (35)
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- A compositional approach to quantum functions
- Perfect Commuting-Operator Strategies for Linear System Games
- A synchronous game for binary constraint systems
- Algebras, Synchronous Games and Chromatic Numbers of Graphs
- Perfect strategies for non-signalling games
- Non-closure of quantum correlation matrices and factorizable channels that require infinite dimensional ancilla
- The quantum-to-classical graph homomorphism game
- Entanglement in non-local games and the hyperlinear profile of groups
- Synchronous correlation matrices and Connes' embedding conjecture
- Linear conic formulations for two-party correlations and values of nonlocal games
- Orthogonal Representations, Projective Rank, and Fractional Minimum Positive Semidefinite Rank: Connections and New Directions
- Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
- Almost synchronous quantum correlations
- Non-closure of the set of quantum correlations via graphs
- Quantum no-signalling correlations and non-local games
- Synchronous linear constraint system games
- Deciding the existence of perfect entangled strategies for nonlocal games
- State convertibility in the von Neumann algebra framework
- Nonlocal games, synchronous correlations, and Bell inequalities
- Noncommutative Nullstellensätze and Perfect Games
- Products of synchronous games
- An operator-algebraic formulation of self-testing
- A category of quantum posets
- Geometry of the set of synchronous quantum correlations
- Discrete quantum structures
- Counterexamples in self-testing
- Quantum symmetry vs nonlocal symmetry
- Maximally entangled correlation sets
- The membership problem for constant-sized quantum correlations is undecidable
- Faithful tracial states on quotients of C*-algebras
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Morphisms in categories of nonlocal games
- Trading symmetry for Hilbert-space dimension in Bell-inequality violation
- Transitive Nonlocal Games