Estimating quantum chromatic numbers
From MaRDI portal
Publication:5963425
DOI10.1016/J.JFA.2016.01.010zbMATH Open1353.46043arXiv1407.6918OpenAlexW2137696127WikidataQ57521786 ScholiaQ57521786MaRDI QIDQ5963425FDOQ5963425
Authors: Vern I. Paulsen, Simone Severini, Daniel Stahlke, Ivan G. Todorov, Andreas Winter 
Publication date: 19 February 2016
Published in: Journal of Functional Analysis (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1407.6918
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
Coloring of graphs and hypergraphs (05C15) Operator spaces and completely bounded maps (46L07) Operator spaces (= matricially normed spaces) (47L25) Operator algebra methods applied to problems in quantum theory (81R15)
Cites Work
- On the quantum chromatic number of a graph
- Title not available (Why is that?)
- On the Shannon capacity of a graph
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- Graph homomorphisms for quantum players
- About the Connes embedding conjecture
- Nuclearity related properties in operator systems
- Quantum chromatic numbers via operator systems
Cited In (50)
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- The Connes embedding problem: a guided tour
- 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)
- 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
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- Quantum and non-signalling graph isomorphisms
- Synchronous linear constraint system games
- On the quantum chromatic number of a graph
- Transitive nonlocal games
- Inductive limits in the operator system and related categories
- Geometry of the set of synchronous quantum correlations
- Perfect commuting-operator strategies for linear system games
- 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
- An operator-algebraic formulation of self-testing
- Universality of graph homomorphism games and the quantum coloring problem
- Matricial Archimedean order unit spaces and quantum correlations
- Synchronous values of games
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Quantum hypergraph homomorphisms and non-local games
- Noncommutative nullstellensätze and perfect games
- A compositional approach to quantum functions
- State convertibility in the von Neumann algebra framework
- 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
- The zero-error side information problem and chromatic numbers (Corresp.)
- Synchronous correlation matrices and Connes' embedding conjecture
- 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
- Almost synchronous quantum correlations
- Positively factorizable maps
- A synchronous game for binary constraint systems
- Spectral lower bounds for the quantum chromatic number of a graph
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- 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
- Quantum no-signalling correlations 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)
