Quantum homomorphisms

DOI10.1016/J.JCTB.2015.12.009MaRDI QIDQ257001zbMATH OpenOpenAlexFDO

Authors L. Mančinska, David Roberson

Publication date 14 March 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.1724

zbMATH Keywords

entangled strategiesgraph coloringgraph homomorphismsLovász thetanonlocal gamequantum chromatic numberquantum graph parameterszero-error communication

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Games involving graphs (91A43)

Abstract: A homomorphism from a graph $X$ to a graph $Y$ is an adjacency preserving mapping $f:V(X)ightarrowV(Y)$. We consider a nonlocal game in which Alice and Bob are trying to convince a verifier with certainty that a graph $X$ admits a homomorphism to $Y$. This is a generalization of the well-studied graph coloring game. Via systematic study of quantum homomorphisms we prove new results for graph coloring. Most importantly, we show that the Lov'{a}sz theta number of the complement lower bounds the quantum chromatic number, which itself is not known to be computable. We also show that some of our newly introduced graph parameters, namely quantum independence and clique numbers, can differ from their classical counterparts while others, namely quantum odd girth, cannot. Finally, we show that quantum homomorphisms closely relate to zero-error channel capacity. In particular, we use quantum homomorphisms to construct graphs for which entanglement-assistance increases their one-shot zero-error capacity.

Recommendations

• Graph homomorphisms for quantum players
• The quantum-to-classical graph homomorphism game
• Quantum chromatic numbers via operator systems
• On the quantum chromatic number of a graph
• Quantum and non-signalling graph isomorphisms

Cites work

• A lower bound on the value of entangled binary games
• Approximate graph coloring by semidefinite programming
• Conic formulations of graph homomorphisms
• Entanglement can increase asymptotic rates of zero-error classical communication over classical channels
• Forbidden Intersections
• Homomorphisms of 3-chromatic graphs
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1054727 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
• New Separations in Zero-Error Channel Capacity Through Projective Kochen–Specker Sets and Quantum Coloring
• On the quantum chromatic number of a graph
• On the Shannon capacity of a graph
• Violating the Shannon capacity of metric graphs with entanglement

Cited in

(54)

• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Non-closure of the set of quantum correlations via graphs
• Sandwich theorems and capacity bounds for non-commutative graphs
• A unified construction of semiring-homomorphic graph invariants
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• A category of quantum posets
• A generalization of Strassen's theorem on preordered semirings
• Spectral lower bounds for the quantum chromatic number of a graph. II
• 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
• Quantum graph homomorphisms via operator systems
• Bounds on entanglement assisted source-channel coding via the Lovász number and its variants
• Graph homomorphisms for quantum players
• Quantum bilinear optimization
• scientific article; zbMATH DE number 5734210 (Why is no real title available?)
• Quantum generalized Harish-Chandra isomorphisms
• A compositional approach to quantum functions
• scientific article; zbMATH DE number 7453174 (Why is no real title available?)
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• The quantum monad on relational structures
• Quantum sets
• Quantum multiplicative graph and a type of separate clique number
• Linear conic formulations for two-party correlations and values of nonlocal games
• Quantum extensions of ordinary maps
• Quantum chromatic numbers via operator systems
• Quantum semigroups from synchronous games
• Exclusivity structures and graph representatives of local complementation orbits
• Extended graphs based on KM-fuzzy metric spaces
• The quantum-to-classical graph homomorphism game
• The core of a complementary prism
• Discrete quantum structures. II: Examples
• Graph isomorphism: physical resources, optimization models, and algebraic characterizations
• Quantum isomorphism of graphs from association schemes
• 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
• Universality of graph homomorphism games and the quantum coloring problem
• The inertia bound is far from tight
• A natural deduction system for orthomodular logic
• Homomorphisms of quantum hypergraphs
• On quantum Cayley graphs
• Quantum advantage and CSP complexity
• A spectral lower bound on chromatic numbers using p-energy
• Quantum chromatic number of products of quantum graphs
• Inertia, independence and expanders
• Eigenvalue bounds for the quantum chromatic number of graph powers
• Quantum advantage and CSP complexity
• Hoffman colorings of graphs
• Satisfiability of commutative vs. non-commutative CSPs
• Thinness of product graphs

This page was built for publication: Quantum homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q257001)