Quantum nonexpander problem is quantum-Merlin-Arthur-complete
Adam D. Bookatz, Stephen P. Jordan, Yi-Kai Liu, Paweł Wocjan · arXiv (Cornell University) · 2012
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 the problem of deciding whether a quantum channel is not rapidly mixing is a complete problem for the quantum Merlin-Arthur complexity class. This has applications to testing randomized constructions of quantum expanders and studying thermalization of open quantum systems.