SEMINAR: Groups and Combinatorics Seminar: Graph homomorphisms for quantum players
|Groups and Combinatorics Seminar: Graph homomorphisms for quantum players
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 https://arxiv.org/abs/1212.1724 which is a joint work with David E. Roberson.
Tue, 14 Apr 2015 16:00
Tue, 14 Apr 2015 17:00
Gabriel Verret <[email protected]>
Fri, 10 Apr 2015 12:08
- Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
- Download this event as:
Mail this event: