Quantum homomorphisms

DOI10.1016/J.JCTB.2015.12.009zbMATH Open1332.05098OpenAlexW3102338202MaRDI QIDQ257001FDOQ257001

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 homomorphismsnonlocal gamequantum chromatic numberquantum graph parameterszero-error communicationLovász theta

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) 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

• 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?)
• 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
• 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 Shannon capacity of a graph
• On the quantum chromatic number of a graph
• Violating the Shannon capacity of metric graphs with entanglement

Cited in

(46)

• A compositional approach to quantum functions
• The quantum-to-classical graph homomorphism game
• Non-closure of the set of quantum correlations via graphs
• A generalization of Strassen's theorem on preordered semirings
• Spectral lower bounds for the quantum chromatic number of a graph
• Quantum chromatic numbers via operator systems
• Sandwich theorems and capacity bounds for non-commutative graphs
• Spectral lower bounds for the quantum chromatic number of a graph. II
• Thinness of product graphs
• Constant-sized robust self-tests for states and measurements of unbounded dimension
• Perfect strategies for non-local games
• Quantum extensions of ordinary maps
• Homomorphisms of quantum hypergraphs
• A unified construction of semiring-homomorphic graph invariants
• Extended graphs based on KM-fuzzy metric spaces
• Transitive nonlocal games
• Spectral lower bounds for the orthogonal and projective ranks of a graph
• Discrete quantum structures. I: Quantum predicate logic
• Quantum no-signalling correlations and non-local games
• Quantum and non-signalling graph isomorphisms
• Quantum isomorphism of graphs from association schemes
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Graph homomorphisms for quantum players
• A natural deduction system for orthomodular logic
• Quantum generalized Harish-Chandra isomorphisms
• The core of a complementary prism
• The quantum monad on relational structures
• Universality of graph homomorphism games and the quantum coloring problem
• Quantum bilinear optimization
• scientific article; zbMATH DE number 7453174 (Why is no real title available?)
• Quantum graph homomorphisms via operator systems
• Quantum sets
• On quantum Cayley graphs
• Linear conic formulations for two-party correlations and values of nonlocal games
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Graph isomorphism: physical resources, optimization models, and algebraic characterizations
• scientific article; zbMATH DE number 5734210 (Why is no real title available?)
• Quantum semigroups from synchronous games
• Bounds on entanglement assisted source-channel coding via the Lovász \(\vartheta\) number and its variants
• Exclusivity structures and graph representatives of local complementation orbits
• A category of quantum posets
• Quantum multiplicative graph and a type of separate clique number
• Discrete quantum structures. II: Examples
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• Quantum hypergraph homomorphisms and non-local games
• The inertia bound is far from tight

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)