Oracle complexity classes and local measurements on physical Hamiltonians

S. Gharibian, S. Piddock, J. Yirka, in: Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), n.d., p. 38.

Conference Paper | Accepted | English
Author
; ;
Department
Abstract
The canonical problem for the class Quantum Merlin-Arthur (QMA) is that of estimating ground state energies of local Hamiltonians. Perhaps surprisingly, [Ambainis, CCC 2014] showed that the related, but arguably more natural, problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM) is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that APX-SIM is P^QMA[log]-complete, for P^QMA[log] the class of languages decidable by a P machine making a logarithmic number of adaptive queries to a QMA oracle. In this work, we show that APX-SIM is P^QMA[log]-complete even when restricted to more physical Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results. We first give a sequence of results which together yield P^QMA[log]-hardness for APX-SIM on well-motivated Hamiltonians: (1) We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. These equalities simplify the proofs of our subsequent results. (2) Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (a la [Cubitt, Montanaro, Piddock, 2017]). As a byproduct, we obtain a full complexity classification of APX-SIM, showing it is complete for P, P^||NP, P^||StoqMA, or P^||QMA depending on the Hamiltonians employed. (3) Leveraging the above, we show that APX-SIM is P^QMA[log]-complete for any family of Hamiltonians which can efficiently simulate spatially sparse Hamiltonians, including physically motivated models such as the 2D Heisenberg model. Our second focus considers 1D systems: We show that APX-SIM remains P^QMA[log]-complete even for local Hamiltonians on a 1D line of 8-dimensional qudits. This uses a number of ideas from above, along with replacing the "query Hamiltonian" of [Ambainis, CCC 2014] with a new "sifter" construction.
Publishing Year
Proceedings Title
Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Page
38
LibreCat-ID

Cite this

Gharibian S, Piddock S, Yirka J. Oracle complexity classes and local measurements on physical  Hamiltonians. In: Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020). ; :38.
Gharibian, S., Piddock, S., & Yirka, J. (n.d.). Oracle complexity classes and local measurements on physical  Hamiltonians. In Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020) (p. 38).
@inproceedings{Gharibian_Piddock_Yirka, title={Oracle complexity classes and local measurements on physical  Hamiltonians}, booktitle={Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, author={Gharibian, Sevag and Piddock, Stephen and Yirka, Justin}, pages={38} }
Gharibian, Sevag, Stephen Piddock, and Justin Yirka. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” In Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 38, n.d.
S. Gharibian, S. Piddock, and J. Yirka, “Oracle complexity classes and local measurements on physical  Hamiltonians,” in Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), p. 38.
Gharibian, Sevag, et al. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), p. 38.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 1909.05981

Search this title in

Google Scholar