Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2014.212
URN: urn:nbn:de:0030-drops-48179
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4817/
Mancinska, Laura ; Roberson, David
Graph Homomorphisms for Quantum Players
| pdf-format: |
|
Abstract
A homomorphism from a graph X to a graph Y is an adjacency preservingmapping 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.
BibTeX - Entry
@InProceedings{mancinska_et_al:LIPIcs:2014:4817,
author = {Laura Mancinska and David Roberson},
title = {{Graph Homomorphisms for Quantum Players}},
booktitle = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
pages = {212--216},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-73-6},
ISSN = {1868-8969},
year = {2014},
volume = {27},
editor = {Steven T. Flammia and Aram W. Harrow},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4817},
URN = {urn:nbn:de:0030-drops-48179},
doi = {10.4230/LIPIcs.TQC.2014.212},
annote = {Keywords: graph homomorphism, nonlocal game, Lov{\'a}sz theta, quantum chromatic number, entanglement}
}
| Keywords: | graph homomorphism, nonlocal game, Lovász theta, quantum chromatic number, entanglement | |
| Seminar: | 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) | |
| Issue date: | 2014 | |
| Date of publication: | 11.12.2014 |
