Testing quantum expanders is co-QMA-complete

TitleTesting quantum expanders is co-QMA-complete
Publication TypeJournal Article
Year of Publication2013
AuthorsBookatz, AD, Jordan, SP, Liu, Y-K, Wocjan, P
JournalPhysical Review A
Date Published2013/4/15

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.

Short TitlePhys. Rev. A