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 PQMA[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 PQMA[log] -complete. In this paper, we continue the study of PQMA[log] , obtaining the following lower and upper bounds.Lower bounds (hardness results): - The PQMA[log] -completeness result of [Ambainis, CCC 2014] requires O(logn) -local observables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5 -local Hamiltonians is PQMA[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 PQMA[log] -complete. - We identify a flaw in [Ambainis, CCC 2014] regarding a PUQMA[log] -hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a ``query validation'' technique, we build on [Ambainis, CCC 2014] to obtain PUQMA[log] -hardness for estimating spectral gaps under polynomial-time Turing reductions. Upper bounds (containment in complexity classes): - PQMA[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 PQMA[log]⊆PP . This improves the containment QMA⊆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.
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 PQMA[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 PQMA[log] -complete. In this paper, we continue the study of PQMA[log] , obtaining the following lower and upper bounds.Lower bounds (hardness results): - The PQMA[log] -completeness result of [Ambainis, CCC 2014] requires O(logn) -local observables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5 -local Hamiltonians is PQMA[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 PQMA[log] -complete. - We identify a flaw in [Ambainis, CCC 2014] regarding a PUQMA[log] -hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a query validation'' technique, we build on [Ambainis, CCC 2014] to obtain PUQMA[log] -hardness for estimating spectral gaps under polynomial-time Turing reductions. Upper bounds (containment in complexity classes): - PQMA[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 PQMA[log]⊆PP . This improves the containment QMA⊆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.
An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, Ambainis 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 results. The P^QMA[log]-completeness result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We show that simulating even a 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. P^QMA[log] is thought of as "slightly harder" than QMA. We justify this formally by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung to show P^QMA[log] \subseteq PP. This improves the containment QMA \subseteq PP from Kitaev and Watrous. A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a "query validation" technique, we build on his prior work to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.
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 results: (1) The P^QMA[log]-completeness result of [Ambainis, CCC 2014] above requires O(log(n))-local Hamiltonians and O(log(n))-local observables. Whether this could be improved to the more physically appealing O(1)-local setting was left as an open question. We resolve this question positively by showing that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete. (2) We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is P^QMA[log]-complete. (3) P^QMA[log] is thought of as slightly harder than QMA. We give a formal justification of this intuition by exploiting the technique of hierarchical voting of [Beigel, Hemachandra, and Wechsung, SCT 1989] to show P^QMA[log] is in PP. This improves the known containment that QMA is in PP [Kitaev, Watrous, STOC 2000]. (4) A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, 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.
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.
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.
We study the computational complexity of estimating the normalized trace 2−nTr[f(A)] for a log-local Hamiltonian A acting on n qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x).
We show that if f(x) is a continuous function with approximate degree Ω(poly(n)), then estimating 2−nTr[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x). This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when A is sparse, the classical query complexity of this problem is exponential in the approximate degree. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.
The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class PQMA[log]: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for PUQMA[log], a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is PQMA[log]-complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of PQMA[log].