TY - JOUR
T1 - Testing quantum expanders is co-QMA-complete
JF - Physical Review A
Y1 - 2013
A1 - Adam D. Bookatz
A1 - Stephen P. Jordan
A1 - Yi-Kai Liu
A1 - Pawel Wocjan
AB - 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.
VL - 87
UR - http://arxiv.org/abs/1210.0787v2
CP - 4
J1 - Phys. Rev. A
U5 - 10.1103/PhysRevA.87.042317
ER -