Estimating quantum chromatic numbers
From MaRDI portal
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
- About the Connes embedding conjecture
- Graph homomorphisms for quantum players
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Nuclearity related properties in operator systems
- On the quantum chromatic number of a graph
- On the Shannon capacity of a graph
- Quantum chromatic numbers via operator systems
Cited in
(69)- Quantum approaches to graph colouring
- On the quantum chromatic number of a graph
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Non-closure of the set of quantum correlations via graphs
- Entanglement in non-local games and the hyperlinear profile of groups
- On the relation between completely bounded and \((1,{cb})\)-summing maps with applications to quantum XOR games
- A category of quantum posets
- 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)
- State convertibility in the von Neumann algebra framework
- Bisynchronous games and factorizable maps
- Positively factorizable maps
- Perfect strategies for non-local games
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- Spectral lower bounds for the quantum chromatic number of a graph
- Quantum and non-signalling graph isomorphisms
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- Synchronous correlation matrices and Connes' embedding conjecture
- Perfect commuting-operator strategies for linear system games
- Geometry of the set of synchronous quantum correlations
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- The zero-error side information problem and chromatic numbers (Corresp.)
- A compositional approach to quantum functions
- Inductive limits in the operator system and related categories
- A synchronous game for binary constraint systems
- Almost synchronous quantum correlations
- Linear conic formulations for two-party correlations and values of nonlocal games
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Quantum chromatic numbers via operator systems
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Synchronous linear constraint system games
- The Connes embedding problem: a guided tour
- The quantum-to-classical graph homomorphism game
- Products of synchronous games
- A Characterization of Perfect Strategies for Mirror 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
- Noncommutative nullstellensätze and perfect games
- Spectral bounds for the quantum chromatic number of quantum graphs
- Matricial Archimedean order unit spaces and quantum correlations
- Quantum hypergraph homomorphisms and non-local games
- Discrete quantum structures. I: Quantum predicate logic
- Quantum no-signalling correlations and non-local games
- Transitive nonlocal games
- Constant-sized robust self-tests for states and measurements of unbounded dimension
- An operator-algebraic formulation of self-testing
- Universality of graph homomorphism games and the quantum coloring problem
- Synchronous values of games
- The universal theory of the hyperfinite \(\mathrm{II}_1\) factor is not computable
- Quantum Mycielski graphs
- Unique games and games based on groups
- Quantum advantage and CSP complexity
- Quantum chromatic number of products of quantum graphs
- Rounding near-optimal quantum strategies for nonlocal games to strategies using a maximally entangled state
- Undecidability and incompleteness in quantum information theory and operator algebras
- Eigenvalue bounds for the quantum chromatic number of graph powers
- Real operator systems
- Approximate traces on groups and the quantum complexity class \(\mathrm{MIP}^{co,s}\)
- Satisfiability problems and algebras of Boolean constraint system games
- The membership problem for constant-sized quantum correlations is undecidable
- On the quantum chromatic numbers of small graphs
- 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 system approach to self-testing
- Joint numerical ranges of three Hermitian 4 4 matrices
- Noncommutative harmonic analysis and quantum information. Abstracts from the workshop held January 25--30, 2026
- Quantum relaxations of CSP and structure isomorphism
- Almost synchronous correlations and Tomita-Takesaki theory
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)
