Vern Paulsen, University of Waterloo
"Complexity and Capacity Bounds for Operator Systems and Quantum Channels"
Shannon introduced the concept of the one-shot zero-error capacity of a classical channel and proved that each such channel had a graph affiliated with it so that the one-shot zero-error capacity was the independence number of the graph. The zero-error capacity is then obtained by taking the k-th root of the strong product of the graph with itself k times and taking the supremum over k. Shannon admittedly couldn’t compute this value for many graphs, but then Lovasz introduced his theta function of a graph as a computable upper bound. The Lovasz theta bound is still the best known bound for this capacity.
Dean, Severini, and Winter studied Shannon’s ideas for quantum channels and proved that each quantum channel has affiliated with it an operator system such that the one-shot zero-error capacity of the channel is the "independence number” of the operator system. They then argued that the analogue of Shannon’s capacity is to take the k-th root of the independence number of the tensor product of the operator system with itself k times and take the supremum over k. They then introduced the analogue of the Lovasz theta function for an operator system.
In this talk we will review these ideas and then introduce our new idea of the "complexity" of an operator system and show that this gives another bound on the zero-error capacity of the quantum channel. We will present several different linear algebraic characterizations of complexity. We will then show that there are some operator systems and quantum channels for which our complexity based bound is better than the Lovasz bound.