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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| 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 |
| _version_ | 1826191753217048576 |
|---|---|
| author | Jordan, Stephen P. Liu, Yi-Kai Wocjan, Pawel Bookatz, Adam D. |
| author2 | Massachusetts Institute of Technology. Center for Theoretical Physics |
| author_facet | Massachusetts Institute of Technology. Center for Theoretical Physics Jordan, Stephen P. Liu, Yi-Kai Wocjan, Pawel Bookatz, Adam D. |
| author_sort | Jordan, Stephen P. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:00:45Z |
| format | Article |
| id | mit-1721.1/88738 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:00:45Z |
| publishDate | 2014 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/887382022-09-30T12:48:35Z Quantum nonexpander problem is quantum-Merlin-Arthur-complete Jordan, Stephen P. Liu, Yi-Kai Wocjan, Pawel Bookatz, Adam D. Massachusetts Institute of Technology. Center for Theoretical Physics Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Department of Physics Bookatz, Adam D. Wocjan, Pawel 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. United States. Dept. of Energy (Cooperative Research Agreement DE-FG02-05ER41360) National Science Foundation (U.S.). Center for Science of Information (Grant CCF-0939370) National Science Foundation (U.S.) (CAREER Award CCF-0746600) 2014-08-15T18:29:29Z 2014-08-15T18:29:29Z 2013-04 2012-12 Article http://purl.org/eprint/type/JournalArticle 1050-2947 1094-1622 http://hdl.handle.net/1721.1/88738 Bookatz, Adam, Stephen Jordan, Yi-Kai Liu, and Pawel Wocjan. “Quantum Nonexpander Problem Is Quantum-Merlin-Arthur-Complete.” Phys. Rev. A 87, no. 4 (April 2013). © 2013 American Physical Society https://orcid.org/0000-0001-9475-2091 en_US http://dx.doi.org/10.1103/PhysRevA.87.042317 Physical Review A Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf American Physical Society American Physical Society |
| spellingShingle | Jordan, Stephen P. Liu, Yi-Kai Wocjan, Pawel Bookatz, Adam D. Quantum nonexpander problem is quantum-Merlin-Arthur-complete |
| title | Quantum nonexpander problem is quantum-Merlin-Arthur-complete |
| title_full | Quantum nonexpander problem is quantum-Merlin-Arthur-complete |
| title_fullStr | Quantum nonexpander problem is quantum-Merlin-Arthur-complete |
| title_full_unstemmed | Quantum nonexpander problem is quantum-Merlin-Arthur-complete |
| title_short | Quantum nonexpander problem is quantum-Merlin-Arthur-complete |
| title_sort | quantum nonexpander problem is quantum merlin arthur complete |
| url | http://hdl.handle.net/1721.1/88738 https://orcid.org/0000-0001-9475-2091 |
| work_keys_str_mv | AT jordanstephenp quantumnonexpanderproblemisquantummerlinarthurcomplete AT liuyikai quantumnonexpanderproblemisquantummerlinarthurcomplete AT wocjanpawel quantumnonexpanderproblemisquantummerlinarthurcomplete AT bookatzadamd quantumnonexpanderproblemisquantummerlinarthurcomplete |