The classical expander mixing lemma (EML) connects two notions of pseudorandomness for graphs. The EML states that spectral expansion (the adjacency matrix having “small second eigenvalue”) implies uniformity (having roughly “the right” number of edges between pairs of vertex subsets). In this talk, we look at a known quantum analogue of the EML, which shows that if a quantum channel is a quantum expander, then it is also an approximate 1-design. In particular, we show a quantum analogue of a recent result of Conlon and Zhao showing that, while converse of the classical EML is false in general, it holds true for all vertex-transitive graphs. Similarly, super-operators (and in particular channels) with sufficient symmetry turn out to allow for a converse quantum EML. Our proof uses the non-commutative Grothendieck inequality.
Based on joint work with Tom Bannink and Jop Briët.