Quantum homomorphisms

详细信息    查看全文

• 作者：Laura Mančinska^a ; ^b ; ¹ ; ^{laura@locc.la" class="auth_mail" title="E-mail the corresponding author} ; David E. Roberson^a ; ² ; ^{davideroberson@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph homomorphisms ; Graph coloring ; Zero-error communication ; Entangled strategies ; Nonlocal game ; Lov&aacute ; sz theta ; Quantum chromatic number ; Quantum graph parameters
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：118
• 期：Complete
• 页码：228-267
• 全文大小：666 K

文摘

A homomorphism from a graph X to a graph Y   is an adjacency preserving map f:V(X)→V(Y)$f:V(X)\to 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 is a lower bound on the quantum chromatic number, the latter of which 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.