Gosset, David and Mehta, Jenish C. and Vidick, Thomas (2017) QCMA hardness of ground space connectivity for commuting Hamiltonians. Quantum, 1 . p. 16. ISSN 2521-327X. doi:10.22331/q-2017-07-14-16. https://resolver.caltech.edu/CaltechAUTHORS:20171011-112512941
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
Creative Commons Attribution. 521kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20171011-112512941
Abstract
In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H. It was shown in [Gharibian and Sikora, ICALP15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.
| Item Type: | Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||
| ORCID: |
| ||||||||||||
| Additional Information: | This paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. T.V. is supported by NSF CAREER grant CCF-1553477 and an AFOSR YIP award number FA9550-16-1-0495. All authors were partially supported by the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). | ||||||||||||
| Group: | Institute for Quantum Information and Matter | ||||||||||||
| Funders: |
| ||||||||||||
| DOI: | 10.22331/q-2017-07-14-16 | ||||||||||||
| Record Number: | CaltechAUTHORS:20171011-112512941 | ||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20171011-112512941 | ||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
| ID Code: | 82282 | ||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||
| Deposited By: | Joy Painter | ||||||||||||
| Deposited On: | 11 Oct 2017 18:41 | ||||||||||||
| Last Modified: | 15 Nov 2021 19:49 |
Repository Staff Only: item control page
