Quantum nonexpander problem is quantum-Merlin-Arthur-complete

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...

Full description

Bibliographic Details
Main Authors: Jordan, Stephen P., Liu, Yi-Kai, Wocjan, Pawel, Bookatz, Adam D.
Other Authors: Massachusetts Institute of Technology. Center for Theoretical Physics
Format: Article
Language:en_US
Published: American Physical Society 2014
Online Access:http://hdl.handle.net/1721.1/88738
https://orcid.org/0000-0001-9475-2091