conference paper
Oracle complexity classes and local measurements on physical Hamiltonians
published
Sevag
Gharibian
author 715410000-0002-9992-3379
Stephen
Piddock
author
Justin
Yirka
author
623
department
7
department
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.
2020
eng
Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)
1909.05981
38
Gharibian S, Piddock S, Yirka J. Oracle complexity classes and local measurements on physical Hamiltonians. In: <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>. ; 2020:38.
@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} }
S. Gharibian, S. Piddock, and J. Yirka, “Oracle complexity classes and local measurements on physical Hamiltonians,” in <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>, 2020, p. 38.
Gharibian, Sevag, et al. “Oracle Complexity Classes and Local Measurements on Physical Hamiltonians.” <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>, 2020, p. 38.
Gharibian, S., Piddock, S., & Yirka, J. (2020). Oracle complexity classes and local measurements on physical Hamiltonians. <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>, 38.
Gharibian, Sevag, Stephen Piddock, and Justin Yirka. “Oracle Complexity Classes and Local Measurements on Physical Hamiltonians.” In <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>, 38, 2020.
S. Gharibian, S. Piddock, J. Yirka, in: Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.
132262019-09-16T07:41:31Z2023-10-09T04:17:41Z