---
res:
bibo_abstract:
- "The canonical problem for the class Quantum Merlin-Arthur (QMA) is that of\r\nestimating
ground state energies of local Hamiltonians. Perhaps surprisingly,\r\n[Ambainis,
CCC 2014] showed that the related, but arguably more natural,\r\nproblem of simulating
local measurements on ground states of local Hamiltonians\r\n(APX-SIM) is likely
harder than QMA. Indeed, [Ambainis, CCC 2014] showed that\r\nAPX-SIM is P^QMA[log]-complete,
for P^QMA[log] the class of languages decidable\r\nby a P machine making a logarithmic
number of adaptive queries to a QMA oracle.\r\nIn this work, we show that APX-SIM
is P^QMA[log]-complete even when restricted\r\nto more physical Hamiltonians,
obtaining as intermediate steps a variety of\r\nrelated complexity-theoretic results.\r\n
\ We first give a sequence of results which together yield P^QMA[log]-hardness\r\nfor
APX-SIM on well-motivated Hamiltonians: (1) We show that for NP, StoqMA,\r\nand
QMA oracles, a logarithmic number of adaptive queries is equivalent to\r\npolynomially
many parallel queries. These equalities simplify the proofs of our\r\nsubsequent
results. (2) Next, we show that the hardness of APX-SIM is preserved\r\nunder
Hamiltonian simulations (a la [Cubitt, Montanaro, Piddock, 2017]). As a\r\nbyproduct,
we obtain a full complexity classification of APX-SIM, showing it is\r\ncomplete
for P, P^||NP, P^||StoqMA, or P^||QMA depending on the Hamiltonians\r\nemployed.
(3) Leveraging the above, we show that APX-SIM is P^QMA[log]-complete\r\nfor any
family of Hamiltonians which can efficiently simulate spatially sparse\r\nHamiltonians,
including physically motivated models such as the 2D Heisenberg\r\nmodel.\r\n
\ Our second focus considers 1D systems: We show that APX-SIM remains\r\nP^QMA[log]-complete
even for local Hamiltonians on a 1D line of 8-dimensional\r\nqudits. This uses
a number of ideas from above, along with replacing the \"query\r\nHamiltonian\"
of [Ambainis, CCC 2014] with a new \"sifter\" construction.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sevag
foaf_name: Gharibian, Sevag
foaf_surname: Gharibian
foaf_workInfoHomepage: http://www.librecat.org/personId=71541
orcid: 0000-0002-9992-3379
- foaf_Person:
foaf_givenName: Stephen
foaf_name: Piddock, Stephen
foaf_surname: Piddock
- foaf_Person:
foaf_givenName: Justin
foaf_name: Yirka, Justin
foaf_surname: Yirka
dct_date: 2020^xs_gYear
dct_language: eng
dct_title: Oracle complexity classes and local measurements on physical Hamiltonians@
...