QMA Lower Bounds for Batch Verification via Approximate Degree
Provides theoretical lower bounds for quantum verification tasks, relevant to complexity theorists studying QMA and batch verification.
The authors prove lower bounds on the witness-query tradeoff for batch verification in QMA, showing that for certain DNF formulas, saving a constant factor in witness length requires a large polynomial increase in query cost. They also obtain new lower bounds for read-once CNF formulas, surjectivity, and k-element distinctness.
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.