Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/87672
Title: Graph homomorphisms for quantum players
Authors: Mančinska, Laura
Roberson, David
Keywords: Graph Homomorphism
Nonlocal Game
DRNTU::Science::Physics
Issue Date: 2014
Source: Mančinska, L., & Roberson, D. (2014). Graph homomorphisms for quantum players. LIPIcs–Leibniz International Proceedings in Informatics, 212-216. doi:10.4230/LIPIcs.TQC.2014.212
Series/Report no.: LIPIcs–Leibniz International Proceedings in Informatics
Abstract: 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.
URI: https://hdl.handle.net/10356/87672
http://hdl.handle.net/10220/46786
DOI: http://dx.doi.org/10.4230/LIPIcs.TQC.2014.212
Rights: © 2014 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Graph Homomorphisms for Quantum Players.pdf304.14 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.