License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4817/
Go to the corresponding LIPIcs Volume Portal

Mancinska, Laura ; Roberson, David

Graph Homomorphisms for Quantum Players

pdf-format:
17.pdf (0.3 MB)

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.

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
Collection: 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)
Issue Date: 2014
Date of publication: 11.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI