Estimating quantum chromatic numbers
From MaRDI portal
Publication:5963425
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
(50)- A compositional approach to quantum functions
- Products of synchronous games
- Quantum approaches to graph colouring
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Spectral bounds for the quantum chromatic number of quantum graphs
- The quantum-to-classical graph homomorphism game
- Non-closure of the set of quantum correlations via graphs
- Matricial Archimedean order unit spaces and quantum correlations
- Spectral lower bounds for the quantum chromatic number of a graph
- Quantum chromatic numbers via operator systems
- Constant-sized robust self-tests for states and measurements of unbounded dimension
- Perfect strategies for non-local games
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Entanglement in non-local games and the hyperlinear profile of groups
- Transitive nonlocal games
- The zero-error side information problem and chromatic numbers (Corresp.)
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- Discrete quantum structures. I: Quantum predicate logic
- The Connes embedding problem: a guided tour
- Quantum no-signalling correlations and non-local games
- Quantum and non-signalling graph isomorphisms
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Synchronous correlation matrices and Connes' embedding conjecture
- Synchronous values of games
- An operator-algebraic formulation of self-testing
- State convertibility in the von Neumann algebra framework
- Universality of graph homomorphism games and the quantum coloring problem
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Almost synchronous quantum correlations
- 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)
- Geometry of the set of synchronous quantum correlations
- Bisynchronous games and factorizable maps
- Perfect commuting-operator strategies for linear system games
- Synchronous linear constraint system games
- Positively factorizable maps
- The universal theory of the hyperfinite \(\mathrm{II}_1\) factor is not computable
- Noncommutative nullstellensätze and perfect games
- A synchronous game for binary constraint systems
- Linear conic formulations for two-party correlations and values of nonlocal games
- Inductive limits in the operator system and related categories
- On the relation between completely bounded and \((1,{cb})\)-summing maps with applications to quantum XOR games
- On the quantum chromatic number of a graph
- A Characterization of Perfect Strategies for Mirror Games
- \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- A category of quantum posets
- A synchronous NPA hierarchy with applications
- Discrete quantum structures. II: Examples
- Quantum hypergraph homomorphisms and 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)
