Testing quantum expanders is co-QMA-complete

Abstract

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.

References in corpus (5)

• Elementary gates for quantum computation
• The power of quantum systems on a line
• N-representability is QMA-complete
• Entropy and Entanglement in Quantum Ground States
• Random Unitaries Give Quantum Expanders