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.
The
ε-approximate degree of a function
f:X→{0,1} is the least degree of a multivariate real polynomial
p such that
∣p(x)−f(x)∣≤ε for all
x∈X. We determine the
ε-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing they are
Θ(n2/3log1/3(1/ε)),
Θ~(n3/4log1/4(1/ε)), and
Θ(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). This improves on the previous best lower bound of
Ω(n1/6) due to Aaronson (Quantum Information & Computation, 2012), and comes somewhat close to matching a known upper bound of
O(n1/3).
We find a quantum oracle relative to which
QMA=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
QMA lower bound to the approximate degree of
OR.