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'asz 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.
Recommendations
- On the quantum chromatic number of a graph
- Quantum chromatic numbers via operator systems
- Spectral bounds for the quantum chromatic number of quantum graphs
- Quantum approaches to graph colouring
- Spectral lower bounds for the quantum chromatic number of a graph
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Spectral lower bounds for the quantum chromatic number of a graph. II
- scientific article; zbMATH DE number 6724468
- Deterministic quantum non-locality and graph colorings
- Estimating the fractional chromatic number of a graph
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- About the Connes embedding conjecture
- Graph homomorphisms for quantum players
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Nuclearity related properties in operator systems
- On the Shannon capacity of a graph
- On the quantum chromatic number of a graph
- Quantum chromatic numbers via operator systems
Cited in
(65)- Quantum no-signalling correlations and non-local games
- Synchronicity for quantum non-local games
- Non-closure of quantum correlation matrices and factorizable channels that require infinite dimensional ancilla (With an appendix by Narutaka Ozawa)
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- The Connes embedding problem: a guided tour
- Entanglement in non-local games and the hyperlinear profile of groups
- A category of quantum posets
- Non-closure of the set of quantum correlations via graphs
- Bisynchronous games and factorizable maps
- Satisfiability problems and algebras of Boolean constraint system games
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- Quantum and non-signalling graph isomorphisms
- On the quantum chromatic number of a graph
- Synchronous linear constraint system games
- Transitive nonlocal games
- Inductive limits in the operator system and related categories
- Geometry of the set of synchronous quantum correlations
- The membership problem for constant-sized quantum correlations is undecidable
- Perfect commuting-operator strategies for linear system games
- On the quantum chromatic numbers of small graphs
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- The quantum-to-classical graph homomorphism game
- Quantum approaches to graph colouring
- Spectral bounds for the quantum chromatic number of quantum graphs
- Products of synchronous games
- Constant-sized robust self-tests for states and measurements of unbounded dimension
- Approximate quantum 3-colorings of graphs and the quantum max 3-cut problem
- The universal theory of locally universal tracial von Neumann algebras is not computable
- An operator-algebraic formulation of self-testing
- Universality of graph homomorphism games and the quantum coloring problem
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Matricial Archimedean order unit spaces and quantum correlations
- Synchronous values of games
- An operator system approach to self-testing
- Quantum Mycielski graphs
- Quantum hypergraph homomorphisms and non-local games
- Undecidability and incompleteness in quantum information theory and operator algebras
- Noncommutative nullstellensätze and perfect games
- State convertibility in the von Neumann algebra framework
- A compositional approach to quantum functions
- On the relation between completely bounded and \((1,{cb})\)-summing maps with applications to quantum XOR games
- A Characterization of Perfect Strategies for Mirror Games
- Synchronous correlation matrices and Connes' embedding conjecture
- The zero-error side information problem and chromatic numbers (Corresp.)
- Unique games and games based on groups
- Quantum advantage and CSP complexity
- Quantum chromatic numbers via operator systems
- Discrete quantum structures. I: Quantum predicate logic
- The universal theory of the hyperfinite \(\mathrm{II}_1\) factor is not computable
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Positively factorizable maps
- Quantum chromatic number of products of quantum graphs
- Rounding near-optimal quantum strategies for nonlocal games to strategies using a maximally entangled state
- Almost synchronous quantum correlations
- A synchronous game for binary constraint systems
- Spectral lower bounds for the quantum chromatic number of a graph
- Eigenvalue bounds for the quantum chromatic number of graph powers
- Real operator systems
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- Approximate traces on groups and the quantum complexity class \(\mathrm{MIP}^{co,s}\)
- 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
- A synchronous NPA hierarchy with applications
- Discrete quantum structures. II: Examples
- Perfect strategies for non-local games
This page was built for publication: Estimating quantum chromatic numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963425)
