SEMINAR: Groups and Combinatorics Seminar: Graph homomorphisms for quantum players


Groups and Combinatorics Seminar: Graph homomorphisms for quantum players 
Other events...

Time and place: 16:00 Tuesday 14 April in Weatherburn LT.
Speaker: Laura Mancinska (National University of Singapore)
Title: Graph homomorphisms for quantum players.
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. Classical players can succeed if and only if X admits a homomorphism to Y. In contrast, entangled quantum players can sometimes succeed even when the corresponding homomorphism does not exist. This motivates the introduction of quantum homomorphisms which turn out to be natural graphtheoretic objects and can also be defined in purely combinatorial terms.
Via systematic study of quantum homomorphisms we prove new results for the previously studied quantum chromatic number. Most importantly, we show that the Lovasz 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 zeroerror channel capacity. In particular, we use quantum homomorphisms to construct graphs for which entanglementassistance increases their oneshot zeroerror capacity. This talk is based on http://arxiv.org/abs/1212.1724 which is a joint work with David E. Roberson.
Contact 
Gabriel Verret
<[email protected]>

Start 
Tue, 14 Apr 2015 16:00

End 
Tue, 14 Apr 2015 17:00

Submitted by 
Gabriel Verret <[email protected]>

Last Updated 
Fri, 10 Apr 2015 12:08

Included in the following Calendars: 

 Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
 Download this event as:
Text 
iCalendar

Mail this event:
