Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2503.02747

A Note on the Complexity of the Spectral Gap Problem

Justin Yirka

Published Mar 4, 2025• 0 citations
arXivHTMLPDF

Abstract

The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class $P^{QMA[log]}$: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for $P^{UQMA[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 $P^{QMA[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 $P^{QMA[log]}$.

Related papers

The complexity of estimating local physical quantities.

Sevag Gharibian, Justin Yirka

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.

•Jun 17, 2016•0 citations

On Physical Problems that are Slightly More Difficult than QMA

Andris Ambainis

We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2014•29 citations

DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians

Zhengfeng Ji, Tongyang Li, Changpeng Shao +2 more

We study the computational complexity of estimating the normalized trace $2^{-n}\mathrm{Tr}[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 $Ω(\mathrm{poly}(n))$, then estimating $2^{-n}\mathrm{Tr}[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.

quant-pharXiv:2604.01519•Apr 3, 2026•0 citations

On physical problems that are slightly more difficult than QMA

Andris Ambainis

We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).

arXiv:1312.4758•Dec 17, 2013•1 citation

The complexity of simulating local measurements on quantum systems

Sevag Gharibian, Justin Yirka

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(log⁡n) -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.

arXiv:1606.05626•Quantum•Sep 30, 2019•16 citations

The Complexity of Stoquastic Sparse Hamiltonians

Alex B. Grilo, Marios Rozos

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.

cs.CCCross-listedarXiv:2605.02845•May 5, 2026•0 citations
The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class PQMA[log]P^{QMA[log]}PQMA[log]: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for PUQMA[log]P^{UQMA[log]}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]P^{QMA[log]}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]P^{QMA[log]}PQMA[log].
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.
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
We study the computational complexity of estimating the normalized trace 2−nTr[f(A)]2^{-n}\mathrm{Tr}[f(A)]2−nTr[f(A)] for a log-local Hamiltonian AAA acting on nnn qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x)f(x)f(x). We show that if f(x)f(x)f(x) is a continuous function with approximate degree Ω(poly(n))Ω(\mathrm{poly}(n))Ω(poly(n)), then estimating 2−nTr[f(A)]2^{-n}\mathrm{Tr}[f(A)]2−nTr[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x)f(x)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 AAA 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.
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
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(log⁡n) -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.
Despite having an unnatural definition, StoqMA\mathsf{StoqMA}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\mathsf{NP}NP, MA\mathsf{MA}MA and AM\mathsf{AM}AM. Therefore, understanding the exact power of StoqMA\mathsf{StoqMA}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\mathsf{StoqSH}StoqSH) is in StoqMA\mathsf{StoqMA}StoqMA. Since Stoquastic Local Hamiltonians are StoqMA\mathsf{StoqMA}StoqMA-hard, this implies that StoqSH\mathsf{StoqSH}StoqSH is StoqMA\mathsf{StoqMA}StoqMA-complete. We complement this result by showing that the separable version of StoqSH\mathsf{StoqSH}StoqSH is StoqMA(2)\mathsf{StoqMA}(2)StoqMA(2)-complete, where StoqMA(2)\mathsf{StoqMA}(2)StoqMA(2) is the version of StoqMA\mathsf{StoqMA}StoqMA that receives two unentangled proofs.