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

Electronic colloquium on computational complexity

QMA Lower Bounds for Approximate Counting.

William Kretschmer

Published Jan 1, 2019• 0 citations
OpenAlex

Related papers

QMA Lower Bounds for Batch Verification via Approximate Degree

Mark Bun, Mandar Juvekar, Samuel King

We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify $m$ copies of a Boolean function $f$ depend on $m$. We give a general technique for proving lower bounds on the witness-query tradeoff needed to batch verify a function $f$ in terms of its approximate degree. Applying this technique to an explicit family of DNF formulas $f$, we show that attempting to save even a constant factor on the witness length of the baseline approach to batch verifying $f$ necessitates a large polynomial increase in the query cost. We also obtain new lower bounds on the QMA query complexity of read-once CNF formulas and on the surjectivity and $k$-element distinctness functions. Our lower bounds also lift to give communication analogs of these results.

arXiv:2607.08888•Leibniz international proceedings in informatics•Jan 1, 2026•1 citation

On approximate counting

Philippe Flajolet

•Jul 1, 1982•4 citations

Approximate Counting

Russ Bubley

Springer eBooks•Jan 1, 2001•0 citations

Vanishing-Error Approximate Degree and QMA Complexity

Alexander A. Sherstov, Justin Thaler

The $ε$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq ε$ for all $x \in X$. We determine the $ε$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing they are $Θ(n^{2/3} \log^{1/3}(1/ε))$, $\tildeΘ(n^{3/4} \log^{1/4}(1/ε))$, and $Θ(n^{1/3} \log^{2/3}(1/ε))$, respectively. Previously, these bounds were known only for constant $ε.$ We also derive a connection between vanishing-error approximate degree and quantum Merlin--Arthur (QMA) query complexity. We use this connection to show that the QMA complexity of permutation testing is $Ω(n^{1/4})$. This improves on the previous best lower bound of $Ω(n^{1/6})$ due to Aaronson (Quantum Information & Computation, 2012), and comes somewhat close to matching a known upper bound of $O(n^{1/3})$.

arXiv:1909.07498•Sep 16, 2019•6 citations

Approximate counting : an alternative approach

Peter Kirschenhofer, Helmut Prodinger

Approximate counting : an alternative approach

RAIRO - Theoretical Informatics and Applications•Jan 1, 1991•20 citations

A quantum oracle separation between QMA(2) and QMA

John Bostanci, Sabee Grewal, Jonas Haferkamp +4 more

We find a quantum oracle relative to which $\mathsf{QMA} \neq \mathsf{QMA}(2)$. As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every $ε+δ<1$, any $(ε,δ)$-disentangler requires input size exponential in the number of output qubits. Our proof combines the unitarily invariant polynomial method of She and Yuen (ITCS '23) with a new construction based on the symmetric and antisymmetric subspace projectors, reducing the $\mathsf{QMA}$ lower bound to the approximate degree of $\mathrm{OR}$.

quant-pharXiv:2609.02865•Sep 3, 2026•4 citations
We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify mmm copies of a Boolean function fff depend on mmm. We give a general technique for proving lower bounds on the witness-query tradeoff needed to batch verify a function fff in terms of its approximate degree. Applying this technique to an explicit family of DNF formulas fff, we show that attempting to save even a constant factor on the witness length of the baseline approach to batch verifying fff necessitates a large polynomial increase in the query cost. We also obtain new lower bounds on the QMA query complexity of read-once CNF formulas and on the surjectivity and kkk-element distinctness functions. Our lower bounds also lift to give communication analogs of these results.
The εεε-approximate degree of a function f ⁣:X→{0,1}f\colon X \to \{0, 1\}f:X→{0,1} is the least degree of a multivariate real polynomial ppp such that ∣p(x)−f(x)∣≤ε|p(x)-f(x)| \leq ε∣p(x)−f(x)∣≤ε for all x∈Xx \in Xx∈X. We determine the εεε-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing they are Θ(n2/3log⁡1/3(1/ε))Θ(n^{2/3} \log^{1/3}(1/ε))Θ(n2/3log1/3(1/ε)), Θ~(n3/4log⁡1/4(1/ε))\tildeΘ(n^{3/4} \log^{1/4}(1/ε))Θ~(n3/4log1/4(1/ε)), and Θ(n1/3log⁡2/3(1/ε))Θ(n^{1/3} \log^{2/3}(1/ε))Θ(n1/3log2/3(1/ε)), respectively. Previously, these bounds were known only for constant ε.ε.ε. We also derive a connection between vanishing-error approximate degree and quantum Merlin--Arthur (QMA) query complexity. We use this connection to show that the QMA complexity of permutation testing is Ω(n1/4)Ω(n^{1/4})Ω(n1/4). This improves on the previous best lower bound of Ω(n1/6)Ω(n^{1/6})Ω(n1/6) due to Aaronson (Quantum Information & Computation, 2012), and comes somewhat close to matching a known upper bound of O(n1/3)O(n^{1/3})O(n1/3).
We find a quantum oracle relative to which QMA≠QMA(2)\mathsf{QMA} \neq \mathsf{QMA}(2)QMA=QMA(2). As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every ε+δ<1ε+δ<1ε+δ<1, any (ε,δ)(ε,δ)(ε,δ)-disentangler requires input size exponential in the number of output qubits. Our proof combines the unitarily invariant polynomial method of She and Yuen (ITCS '23) with a new construction based on the symmetric and antisymmetric subspace projectors, reducing the QMA\mathsf{QMA}QMA lower bound to the approximate degree of OR\mathrm{OR}OR.