Abstract

Duan, Severini, and Winter proposed the study of a specific matrix space as a quantum generalization of graphs, which allows for the formulation and study of a quantum version of Shannon’s zero-error capacity problem. In this talk, we further develop the combinatorial theory of matrix spaces through the lens of graph theory. Initially, we introduce basic correspondences between matrix space properties and graph-theoretical properties, such as nilpotency versus acyclicity, irreducibility versus connectivity, and dimension expansion versus vertex expansion. Subsequently, we demonstrate how these correspondences can be enhanced to the so-called inherited correspondences, which lead to extremal problems for matrix spaces and have applications in invariant theory and noncommutative algebra. Finally, we discuss applications in quantum information processing and provide examples of graph-theoretic properties that are no longer valid in the matrix space setting.