A tale of communication, entanglement and graphs

Math/CS Seminar - Olivier Lalonde - Université de Montréal

Quantum communication complexity, which concerns itself with determining how much communication is required by two participants having access to quantum resources to compute a boolean function of their inputs, has long been a lively subfield of quantum information science. The topic of this talk will be the power of shared prior entanglement relative to quantum communication without prior entanglement, which, despite having been studied for more twenty years, remains rather mysterious. After a quick review of the bare bones of classical communication complexity, I will proceed to discuss the model of entanglement-assisted communication complexity. Notably, while prior entanglement in communication complexity has always been modelled in the finite-dimensional setting, there is no intrinsic reason for this, and communication complexity in the commuting operators model will also be addressed, including a very simple proof of the Holevo-Nayak-Salzman bound in this context. I will then talk about the topic of one-way, exact communication complexity, which, as it turns out, is very strongly tied with the topic of quantum graph theory, for which a crash course will be provided, and showcase two problems for which entanglement-assisted communication is very modestly stronger than quantum communication without prior entanglement coming from this line of research. I will then conclude by mentioning a number of open problems, including whether unconditionally secure quantum bit commitment is possible.