---
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@
...