An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, [Ambainis, CCC 2014] defined the complexity class ${P}^{{QMA}[{log}]}$, and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is ${P}^{{QMA}[{log}]}$-complete. In this paper, we continue the study of ${P}^{{QMA}[{log}]}$, obtaining the following lower and upper bounds.Lower bounds (hardness results): - The ${P}^{{QMA}[{log}]}$-completeness result of [Ambainis, CCC 2014] requires $O(log n)$-local observables and Hamiltonians. We show that simulating even a $extit{single qubit}$ measurement on ground states of $5$-local Hamiltonians is ${P}^{{QMA}[{log}]}$-complete, resolving an open question of Ambainis.- We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly ${P}^{{QMA}[{log}]}$-complete. - We identify a flaw in [Ambainis, CCC 2014] regarding a ${P}^{{UQMA}[{log}]}$-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a ``query validation'' technique, we build on [Ambainis, CCC 2014] to obtain ${P}^{{UQMA}[{log}]}$-hardness for estimating spectral gaps under polynomial-time Turing reductions. Upper bounds (containment in complexity classes): - ${P}^{{QMA}[{log}]}$ is thought of as ``slightly harder'' than QMA. We justify this formally by exploiting the hierarchical voting technique of [Beigel, Hemachandra, Wechsung, SCT 1989] to show ${P}^{{QMA}[{log}]}subseteq {PP}$. This improves the containment ${QMA}subseteq {PP}$ [Kitaev, Watrous, STOC 2000]. This work contributes a rigorous treatment of the subtlety involved in studying oracle classes in which the oracle solves a $promise$ problem. This is particularly relevant for quantum complexity theory, where most natural classes such as BQP and QMA are defined as promise classes.
展开▼
