Despite having an unnatural definition, $\mathsf{StoqMA}$ plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of $\mathsf{NP}$, $\mathsf{MA}$ and $\mathsf{AM}$. Therefore, understanding the exact power of $\mathsf{StoqMA}$ (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem ($\mathsf{StoqSH}$) is in $\mathsf{StoqMA}$. Since Stoquastic Local Hamiltonians are $\mathsf{StoqMA}$-hard, this implies that $\mathsf{StoqSH}$ is $\mathsf{StoqMA}$-complete. We complement this result by showing that the separable version of $\mathsf{StoqSH}$ is $\mathsf{StoqMA}(2)$-complete, where $\mathsf{StoqMA}(2)$ is the version of $\mathsf{StoqMA}$ that receives two unentangled proofs.
Despite having an unnatural definition, StoqMA plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of NP, MA and AM. Therefore, understanding the exact power of StoqMA (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem (StoqSH) is in StoqMA. Since Stoquastic Local Hamiltonians are StoqMA-hard, this implies that StoqSH is StoqMA-complete. We complement this result by showing that the separable version of StoqSH is StoqMA(2)-complete, where StoqMA(2) is the version of StoqMA that receives two unentangled proofs.
The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.
We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is StoqMA-complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove coNP-hardness of deciding global stoquasticity in a fixed basis and Σ2p-hardness of deciding global stoquasticity under single-qubit transformations. As a last result, we expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D XYZ Hamiltonians.
The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in NP for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is QMA-complete.
CLH is complete for the complexity class QIMA, defined through quantum verifiers whose local gates commute. Therefore, CLH is QMA-complete if and only if QIMA=QMA. In this work, we introduce a classical-oracle analogue QIMAO and construct a classical oracle O such that BQPO⊆QIMAO.
Since BQPO⊆QMAO for any classical oracle O, this implies QIMAO=QMAO for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is BQP-hard, and hence also against the possibility that it is QMA-complete.
Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).
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.
Stoquasticity, originating in sign-problem-free physical systems, gives rise to StoqMA, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between MA and AM. Unentanglement similarly gives rise to QMA(2), introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes QMA to two unentangled proofs and still has only the trivial NEXP upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via StoqMA(2), the class of unentangled stoquastic Merlin--Arthur proof systems. Beyond its complexity-theoretic interest, StoqMA(2) is connected to the optimality of non-negative tensor optimization algorithms. We highlight:
1. NP⊆StoqMA(2) with O(n)-qubit proofs and completenes 1−2−polylog(n). Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for StoqMA(2). Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH.
2. For logarithmic-size proofs, NP⊆StoqMA(2)log with completeness 1−O(n−2) and vanishing gap, while StoqMA(2)log⊆MA. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption MA=NP.
3. For StoqMA(2)1, the parameter dependence in the general ETH-optimal time bound can be exponentially improved, or the bound achieved simultaneously with polynomial space.
Our lower bounds are obtained by stoquastizing the short-proof QMA(2) protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.