Entanglement-assisted homomorphisms

David Roberson

Abstract

This talk reports on a joint work with Toby Cubitt, Laura Mancinska, Simone Severini, Dan Stahlke, and Andreas Winter.

In this talk we discuss a communication task which provides an operational view of graph homomorphisms. For the task, Alice must communicate (without error) to Bob the output of a joint source through the use of a noisy channel. One can construct graphs which are naturally related to the source and channel respectively, and the problem of communicating a single source output through one use of the channel is equivalent to the existence of a homomorphism from the source graph to the channel graph. One can also consider the asymptotic case, and when the source provides no side information to Bob, this reduces to the problem of computing Shannon capacity.

If Alice and Bob are allowed to share and perform measurements on an entangled quantum state, then it is sometime possible to successfully perform the above