Oracle complexity classes and local measurements on physical Hamiltonians

S. Gharibian, S. Piddock, J. Yirka, ArXiv:1909.05981 (2019).

Preprint | 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
Journal Title
arXiv:1909.05981
Page
38
LibreCat-ID

Cite this

Gharibian S, Piddock S, Yirka J. Oracle complexity classes and local measurements on physical  Hamiltonians. arXiv:190905981. 2019.
Gharibian, S., Piddock, S., & Yirka, J. (2019). Oracle complexity classes and local measurements on physical  Hamiltonians. ArXiv:1909.05981.
@article{Gharibian_Piddock_Yirka_2019, title={Oracle complexity classes and local measurements on physical  Hamiltonians}, journal={arXiv:1909.05981}, author={Gharibian, Sevag and Piddock, Stephen and Yirka, Justin}, year={2019} }
Gharibian, Sevag, Stephen Piddock, and Justin Yirka. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” ArXiv:1909.05981, 2019.
S. Gharibian, S. Piddock, and J. Yirka, “Oracle complexity classes and local measurements on physical  Hamiltonians,” arXiv:1909.05981. 2019.
Gharibian, Sevag, et al. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” ArXiv:1909.05981, 2019.

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