---
_id: '13226'
abstract:
- lang: eng
text: "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."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Stephen
full_name: Piddock, Stephen
last_name: Piddock
- first_name: Justin
full_name: Yirka, Justin
last_name: Yirka
citation:
ama: '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)*. ; 2020:38.'
apa: Gharibian, S., Piddock, S., & Yirka, J. (2020). Oracle complexity classes
and local measurements on physical Hamiltonians. *Proceedings of the 37th Symposium
on Theoretical Aspects of Computer Science (STACS 2020)*, 38.
bibtex: '@inproceedings{Gharibian_Piddock_Yirka_2020, 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}, year={2020}, pages={38} }'
chicago: 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, 2020.
ieee: 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)*, 2020, p. 38.
mla: 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)*, 2020, p. 38.
short: 'S. Gharibian, S. Piddock, J. Yirka, in: Proceedings of the 37th Symposium
on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.'
date_created: 2019-09-16T07:41:31Z
date_updated: 2023-10-09T04:17:41Z
department:
- _id: '623'
- _id: '7'
external_id:
arxiv:
- '1909.05981'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1909.05981
oa: '1'
page: '38'
publication: Proceedings of the 37th Symposium on Theoretical Aspects of Computer
Science (STACS 2020)
publication_status: published
status: public
title: Oracle complexity classes and local measurements on physical Hamiltonians
type: conference
user_id: '71541'
year: '2020'
...