Quantum homomorphisms

DOI10.1016/j.jctb.2015.12.009zbMath1332.05098arXiv1212.1724OpenAlexW3102338202MaRDI QIDQ257001

Laura Mančinska, David E. 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

graph coloringgraph homomorphismsentangled strategiesLovász thetanonlocal gamequantum chromatic numberquantum graph parameterszero-error communication

Mathematics Subject Classification ID

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

Related Items (29)

The quantum-to-classical graph homomorphism game ⋮ Thinness of product graphs ⋮ Extended graphs based on KM-fuzzy metric spaces ⋮ Quantum Bilinear Optimization ⋮ Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization ⋮ A generalization of Strassen's theorem on preordered semirings ⋮ A compositional approach to quantum functions ⋮ Quantum and non-signalling graph isomorphisms ⋮ The core of a complementary prism ⋮ Discrete quantum structures. II: Examples ⋮ Quantum isomorphism of graphs from association schemes ⋮ Quantum hypergraph homomorphisms and non-local games ⋮ Discrete quantum structures. I: Quantum predicate logic ⋮ Unnamed Item ⋮ Spectral lower bounds for the quantum chromatic number of a graph. II ⋮ Quantum semigroups from synchronous games ⋮ Non-closure of the set of quantum correlations via graphs ⋮ Quantum sets ⋮ Quantum multiplicative graph and a type of separate clique number ⋮ Linear conic formulations for two-party correlations and values of nonlocal games ⋮ Spectral upper bound on the quantum k-independence number of a graph ⋮ Unnamed Item ⋮ A unified construction of semiring-homomorphic graph invariants ⋮ Quantum extensions of ordinary maps ⋮ Perfect strategies for non-local games ⋮ Optimization of eigenvalue bounds for the independence and chromatic number of graph powers ⋮ Spectral lower bounds for the orthogonal and projective ranks of a graph ⋮ Spectral lower bounds for the quantum chromatic number of a graph ⋮ A category of quantum posets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conic formulations of graph homomorphisms
• Entanglement can increase asymptotic rates of zero-error classical communication over classical channels
• On the quantum chromatic number of a graph
• Homomorphisms of 3-chromatic graphs
• New Separations in Zero-Error Channel Capacity Through Projective Kochen–Specker Sets and Quantum Coloring
• Forbidden Intersections
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Violating the Shannon capacity of metric graphs with entanglement
• Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number

This page was built for publication: Quantum homomorphisms