%0 Journal Article
%J Physical Review A
%D 2013
%T Testing quantum expanders is co-QMA-complete
%A Adam D. Bookatz
%A Stephen P. Jordan
%A Yi-Kai Liu
%A Pawel Wocjan
%X 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.
%B Physical Review A
%V 87
%8 2013/4/15
%G eng
%U http://arxiv.org/abs/1210.0787v2
%N 4
%! Phys. Rev. A
%R 10.1103/PhysRevA.87.042317