@article {1402, title = {Testing quantum expanders is co-QMA-complete}, journal = {Physical Review A}, volume = {87}, year = {2013}, month = {2013/4/15}, abstract = { 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. }, doi = {10.1103/PhysRevA.87.042317}, url = {http://arxiv.org/abs/1210.0787v2}, author = {Adam D. Bookatz and Stephen P. Jordan and Yi-Kai Liu and Pawel Wocjan} }