Testing quantum expanders is co-QMA-complete

A quantum expander is a unital quantum channel that is rapidly mixing, has
only a few Kraus operators, and can be implemented efficiently on a quantum
computer. We consider the problem of estimating the mixing time (i.e., the
spectral gap) of a quantum expander. We show that this problem is
co-QMA-complete. This has applications to testing randomized constructions of
quantum expanders, and studying thermalization of open quantum systems.