00882nas a2200157 4500008004100000245004900041210004700090260001400137490000700151520044900158100002200607700002400629700001600653700001800669856003700687 2013 eng d00aTesting quantum expanders is co-QMA-complete0 aTesting quantum expanders is coQMAcomplete c2013/4/150 v873 a 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.
1 aBookatz, Adam, D.1 aJordan, Stephen, P.1 aLiu, Yi-Kai1 aWocjan, Pawel uhttp://arxiv.org/abs/1210.0787v2