QLunch with Yinan Li
Speaker: Yinan Li from CWI
Title: The Haemers Bound of Graphs and Noncommutative Graphs, and Quantum Shannon Capacities
Abstract:
Abstract: The Haemers bound of a graph is an important upper bound on the Shannon capacity. It has been used to show that the Shannon capacity is not multiplicative and not additive. In the study of entanglement-assisted zero-error communication, the Haemers bound also plays a central role in separating the Shannon capacity and entanglement-assisted Shannon capacity. In this talk, I will present two new results related to the Haemers bound:
- The Haemers bound over (the reals) is an upper bound on the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (defined through the graph nonlocal game). In other words, the logarithm of the real Haemers bound is an upper bound on the zero-error capacity assisted by maximally entangled state and projective measurement. This is in contrast to the finite field case.
- We give the first definition of the Haemers bound of noncommutative graphs, and prove it upper bounds the Shannon capacity of noncommutative graphs. We also compare our upper bound with other known upper bounds of the noncommutative Shannon capacity.