Yi-Kai Liu, Stephen P. Jordan, Pawel Wocjan, Adam Bookatz
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.
, Jordan, S.
, Wocjan, P.
and Bookatz, A.
Testing quantum expanders is co-QMA-complete, Theory of Computing Systems, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=912561
(Accessed November 29, 2023)