QMA Lower Bounds for Batch Verification via Approximate Degree
2026-07-09 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study how to check many copies of a Boolean function quickly when given a special quantum witness, focusing on understanding the resources needed as the number of copies grows. They develop a method to prove lower limits on the tradeoff between witness length and query number, based on a function's approximate degree. Using this method, they show that for certain functions, reducing the witness size even a little requires a large increase in queries. They also prove new lower bounds for other specific functions and extend these results to related communication problems.
QMABoolean functionquery complexitywitness lengthapproximate degreeDNF formulasCNF formulasquantum communication complexityk-element distinctnesssurjectivity function
Authors
Mark Bun, Mandar Juvekar, Samuel King
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.