License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.20
URN: urn:nbn:de:0030-drops-118818
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11881/
Go to the corresponding LIPIcs Volume Portal


Gharibian, Sevag ; Piddock, Stephen ; Yirka, Justin

Oracle Complexity Classes and Local Measurements on Physical Hamiltonians

pdf-format:
LIPIcs-STACS-2020-20.pdf (0.8 MB)


Abstract

The canonical hard problems for NP and its quantum analogue, Quantum Merlin-Arthur (QMA), are MAX-k-SAT and the k-local Hamiltonian problem (k-LH), the quantum generalization of MAX-k-SAT, respectively. In recent years, however, an arguably even more physically motivated problem than k-LH has been formalized - the problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM). Perhaps surprisingly, [Ambainis, CCC 2014] showed that 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 physically motivated Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results.
Specifically, we first give a sequence of results which together yield P^{QMA[log]}-hardness for APX-SIM on well-motivated Hamiltonians such as the 2D Heisenberg model:
- We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. Formally, P^{NP[log]}=P^{||NP}, P^{StoqMA[log]}=P^{||StoqMA}, and P^{QMA[log]}=P^{||QMA}. (The result for NP was previously shown using a different proof technique.) These equalities simplify the proofs of our subsequent results.
- Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (à la [Cubitt, Montanaro, Piddock, 2017]) by studying a seemingly weaker problem, ∀-APX-SIM. 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.
- 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. This implies APX-SIM is P^{QMA[log]}-complete even on 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.

BibTeX - Entry

@InProceedings{gharibian_et_al:LIPIcs:2020:11881,
  author =	{Sevag Gharibian and Stephen Piddock and Justin Yirka},
  title =	{{Oracle Complexity Classes and Local Measurements on Physical Hamiltonians}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{20:1--20:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11881},
  URN =		{urn:nbn:de:0030-drops-118818},
  doi =		{10.4230/LIPIcs.STACS.2020.20},
  annote =	{Keywords: Quantum Merlin Arthur (QMA), simulation of local measurement, local Hamiltonian, oracle complexity class, physical Hamiltonians}
}

Keywords: Quantum Merlin Arthur (QMA), simulation of local measurement, local Hamiltonian, oracle complexity class, physical Hamiltonians
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI