UWA Logo What's On at UWA
   UWA HomeProspective Students  | Current Students  | Staff  | Alumni  | Visitors  | About  |     Search UWA    for      

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

* Login to add events... *
Today's date is Thursday, May 06, 2021
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 graph-theoretic 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 zero-error channel capacity. In particular, we use quantum homomorphisms to construct graphs for which entanglement-assistance increases their one-shot zero-error 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:
Additional Information:
  • 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:

Top of Page
© 2001-2010  The University of Western Australia
Questions? Mail [email protected]