2026-08-17T09:54:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4817 2024-03-06T10:35:13Z ddc:004 open_access

Graph Homomorphisms for Quantum Players Mancinska, Laura Roberson, David graph homomorphism nonlocal game Lovász theta quantum chromatic number entanglement A homomorphism from a graph X to a graph Y is an adjacency preserving mapping f:V(X) -> V(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ász theta number of the complement lower bounds the quantum chromatic number, which itself is not known to be computable. We also show that other quantum graph parameters, such as quantum independence number, can differ from their classical counterparts. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laura Mancinska and David Roberson 2014 Is Part Of LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2014.212 urn:nbn:de:0030-drops-48179 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.212 eng https://creativecommons.org/licenses/by/3.0/legalcode