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:2607.08888 · Leibniz international proceedings in informatics

QMA Lower Bounds for Batch Verification via Approximate Degree

Mark Bun, Mandar Juvekar, Samuel King

Published Jan 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.approx/random.2026.69

Related papers

Algorithmic Polynomials

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a novel, first-principles approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: $O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})$ for the $k$-element distinctness problem; $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; and $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $\Theta(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $\Omega(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

SIAM Journal on Computing•Jan 1, 2020•4 citations

Algorithmic Polynomials

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - $O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)$ for the $k$-element distinctness problem; - $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; - $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; - $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $Θ(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $Ω(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

arXiv:1801.04607•Jan 14, 2018•0 citations

The Approximate Degree of DNF and CNF Formulas

Alexander A. Sherstov

Abstract. The approximate degree of a Boolean function [Formula: see text] is the minimum degree of a real polynomial [Formula: see text] that approximates [Formula: see text] pointwise: [Formula: see text] for all [Formula: see text]. For every [Formula: see text] we construct conjunctive normal form (CNF) and disjunctive normal form (DNF) formulas of polynomial size with approximate degree [Formula: see text] essentially matching the trivial upper bound of [Formula: see text]. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits [Formula: see text] a question that has seen extensive research over the past 10 years. Prior to our work, an [Formula: see text] lower bound was known only for [Formula: see text] circuits of depth that grows with [Formula: see text] (M. Bun and J. Thaler, SIAM J. Comput., 49 (2020), pp. FOCS17-59–FOCS17-96). Furthermore, the CNF and DNF formulas that we construct are the simplest possible in that they have constant width. Our proof departs significantly from previous approaches and contributes a novel, number-theoretic method for amplifying approximate degree. Our main result remains valid even for one-sided approximation: for any [Formula: see text], we construct a polynomial-size constant-width CNF formula with one-sided approximate degree [Formula: see text]. We thus obtain the following nearly tight separations: [Formula: see text] versus [Formula: see text] for the one-sided versus two-sided approximate degree of a function and [Formula: see text] versus [Formula: see text] for the one-sided approximate degree of a function [Formula: see text] versus its negation [Formula: see text]. As an application, we essentially settle the communication complexity of [Formula: see text] circuits in the bounded-error quantum model, [Formula: see text]-party number-on-the-forehead randomized model, and [Formula: see text]-party number-on-the-forehead nondeterministic model: we prove that for every [Formula: see text], these models require [Formula: see text], [Formula: see text], and [Formula: see text], respectively, bits of communication even for polynomial-size constant-width CNF formulas. In particular, we show that the multiparty communication class [Formula: see text] can be separated near-optimally from [Formula: see text] and [Formula: see text] by a particularly simple function, a polynomial-size constant-width CNF formula.

SIAM Journal on Computing•Jun 10, 2025•1 citation

Approximate Degree Lower Bounds for Oracle Identification Problems

Mark Bun, Nadiia Voronova

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string $x \in \{0, 1\}^n$ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of $x$. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of $Ω(n/\log^2 n)$ for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.

arXiv:2303.03921•Leibniz international proceedings in informatics•Jan 1, 2023•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•3 citations

The Approximate Degree of DNF and CNF Formulas

Alexander A. Sherstov

The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $δ>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $Ω(n^{1-δ}),$ essentially matching the trivial upper bound of $n.$ This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits ($\text{AC}^0$), a question that has seen extensive research over the past 10 years. Previously, an $Ω(n^{1-δ})$ lower bound was known only for $\text{AC}^0$ circuits of depth that grows with $1/δ$ (Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further consequences. (i) We essentially settle the communication complexity of $\text{AC}^0$ circuits in the bounded-error quantum model, $k$-party number-on-the-forehead randomized model, and $k$-party number-on-the-forehead nondeterministic model: we prove that for every $δ>0$, these models require $Ω(n^{1-δ})$, $Ω(n/4^kk^2)^{1-δ}$, and $Ω(n/4^kk^2)^{1-δ}$, respectively, bits of communication even for polynomial-size constant-width CNF formulas. (ii) In particular, we show that the multiparty communication class $\text{coNP}_k$ can be separated essentially optimally from $\text{NP}_k$ and $\text{BPP}_k$ by a particularly simple function, a polynomial-size constant-width CNF. (iii) We give an essentially tight separation, of $O(1)$ versus $Ω(n^{1-δ})$, for the one-sided versus two-sided approximate degree of a function; and $O(1)$ versus $Ω(n^{1-δ})$ for the one-sided approximate degree of a function $f$ versus its negation $\neg f$.

arXiv:2209.01584•Sep 4, 2022•0 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 Boolean function f(x1,x2,…,xn)f(x_{1},x_{2},\ldots,x_{n})f(x1​,x2​,…,xn​) is the minimum degree of a real polynomial that approximates fff pointwise within 1/31/31/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a novel, first-principles approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: O(n34−14(2k−1))O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})O(n43​−4(2k−1)1​) for the kkk-element distinctness problem; O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for the kkk-subset sum problem; O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for any kkk-DNF or kkk-CNF formula; and O(n3/4)O(n^{3/4})O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n)\Theta(n)Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n)\Omega(n)Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
The approximate degree of a Boolean function f(x1,x2,…,xn)f(x_{1},x_{2},\ldots,x_{n})f(x1​,x2​,…,xn​) is the minimum degree of a real polynomial that approximates fff pointwise within 1/31/31/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - O(n34−14(2k−1))O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)O(n43​−4(2k−1)1​) for the kkk-element distinctness problem; - O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for the kkk-subset sum problem; - O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for any kkk-DNF or kkk-CNF formula; - O(n3/4)O(n^{3/4})O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n)Θ(n)Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n)Ω(n)Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
Abstract. The approximate degree of a Boolean function [Formula: see text] is the minimum degree of a real polynomial [Formula: see text] that approximates [Formula: see text] pointwise: [Formula: see text] for all [Formula: see text]. For every [Formula: see text] we construct conjunctive normal form (CNF) and disjunctive normal form (DNF) formulas of polynomial size with approximate degree [Formula: see text] essentially matching the trivial upper bound of [Formula: see text]. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits [Formula: see text] a question that has seen extensive research over the past 10 years. Prior to our work, an [Formula: see text] lower bound was known only for [Formula: see text] circuits of depth that grows with [Formula: see text] (M. Bun and J. Thaler, SIAM J. Comput., 49 (2020), pp. FOCS17-59–FOCS17-96). Furthermore, the CNF and DNF formulas that we construct are the simplest possible in that they have constant width. Our proof departs significantly from previous approaches and contributes a novel, number-theoretic method for amplifying approximate degree. Our main result remains valid even for one-sided approximation: for any [Formula: see text], we construct a polynomial-size constant-width CNF formula with one-sided approximate degree [Formula: see text]. We thus obtain the following nearly tight separations: [Formula: see text] versus [Formula: see text] for the one-sided versus two-sided approximate degree of a function and [Formula: see text] versus [Formula: see text] for the one-sided approximate degree of a function [Formula: see text] versus its negation [Formula: see text]. As an application, we essentially settle the communication complexity of [Formula: see text] circuits in the bounded-error quantum model, [Formula: see text]-party number-on-the-forehead randomized model, and [Formula: see text]-party number-on-the-forehead nondeterministic model: we prove that for every [Formula: see text], these models require [Formula: see text], [Formula: see text], and [Formula: see text], respectively, bits of communication even for polynomial-size constant-width CNF formulas. In particular, we show that the multiparty communication class [Formula: see text] can be separated near-optimally from [Formula: see text] and [Formula: see text] by a particularly simple function, a polynomial-size constant-width CNF formula.
The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string x∈{0,1}nx \in \{0, 1\}^nx∈{0,1}n given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of xxx. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of Ω(n/log⁡2n)Ω(n/\log^2 n)Ω(n/log2n) for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
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).
The approximate degree of a Boolean function f ⁣:{0,1}n→{0,1}f\colon\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} is the minimum degree of a real polynomial ppp that approximates fff pointwise: ∣f(x)−p(x)∣≤1/3|f(x)-p(x)|\leq1/3∣f(x)−p(x)∣≤1/3 for all x∈{0,1}n.x\in\{0,1\}^n.x∈{0,1}n. For every δ>0,δ>0,δ>0, we construct CNF and DNF formulas of polynomial size with approximate degree Ω(n1−δ),Ω(n^{1-δ}),Ω(n1−δ), essentially matching the trivial upper bound of n.n.n. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits (AC0\text{AC}^0AC0), a question that has seen extensive research over the past 10 years. Previously, an Ω(n1−δ)Ω(n^{1-δ})Ω(n1−δ) lower bound was known only for AC0\text{AC}^0AC0 circuits of depth that grows with 1/δ1/δ1/δ (Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further consequences. (i) We essentially settle the communication complexity of AC0\text{AC}^0AC0 circuits in the bounded-error quantum model, kkk-party number-on-the-forehead randomized model, and kkk-party number-on-the-forehead nondeterministic model: we prove that for every δ>0δ>0δ>0, these models require Ω(n1−δ)Ω(n^{1-δ})Ω(n1−δ), Ω(n/4kk2)1−δΩ(n/4^kk^2)^{1-δ}Ω(n/4kk2)1−δ, and Ω(n/4kk2)1−δΩ(n/4^kk^2)^{1-δ}Ω(n/4kk2)1−δ, respectively, bits of communication even for polynomial-size constant-width CNF formulas. (ii) In particular, we show that the multiparty communication class coNPk\text{coNP}_kcoNPk​ can be separated essentially optimally from NPk\text{NP}_kNPk​ and BPPk\text{BPP}_kBPPk​ by a particularly simple function, a polynomial-size constant-width CNF. (iii) We give an essentially tight separation, of O(1)O(1)O(1) versus Ω(n1−δ)Ω(n^{1-δ})Ω(n1−δ), for the one-sided versus two-sided approximate degree of a function; and O(1)O(1)O(1) versus Ω(n1−δ)Ω(n^{1-δ})Ω(n1−δ) for the one-sided approximate degree of a function fff versus its negation ¬f\neg f¬f.