QMA Lower Bounds for Batch Verification via Approximate Degree

Jul 16, 2026

Upload by Miles

Batch verification in QMA query and communication complexity examines how resources scale when verifying m copies of a Boolean function f. A general technique is developed to prove lower bounds on the witness–query tradeoff required for batch verification, expressed through f’s approximate degree. For an explicit DNF family, even constant-factor reductions in witness length force polynomial increases in query cost. Additional lower bounds apply to QMA query complexity of read-once CNF formulas and to surjectivity and k-element distinctness, with communication counterparts.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages28

Reading Time1 h 11 min

Introduction

Batch verification problem and baseline strategies

Background: prior results and related cryptographic links

QMA query model and definition of cost

Batch verification formulation and first main result

QMA Lower Bounds for Batch Verification via Approximate Degree Mark Bun Boston University [mbun@bu. edu](mbun@bu. edu) Mandar Juvekar Boston University [mandarj@bu. edu](mandarj@bu. edu) Samuel King Georgetown University [sik29@georgetown. edu](sik29@georgetown. edu) arXiv :2607 .08888v 1 [ cs .CC] 9 Jul 2026 July 9, 2026 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. 1 Introduction A powerful but untrusted server wants to convince a computationally constrained client that it has correctly performed a large list of computations that were delegated to it. It can do so by proving to the client the veracity of m statements x 1 , . . . , xm. As communication is costly, the proof must be as short as possible. If the statements are instances of an NP (or more generally for this work, QMA) language, a baseline strategy is to send as a proof witnesses w 1 , . . . , wm for all of the statements—the client can then verify each statement individually. Both the communication and the client’s computational cost in this strategy are m times the cost for a single statement. For what statements is it possible to do better? What tradeoffs are achievable between communication and computation? This batch verification problem has generated exciting research in complexity theory and cryptography. Highly communication-efficient interactive proofs are known for batch verifying UP statements (i.e., NP statements with unique witnesses) [RRR16, RRR18, RR20], while a connection between batch verification and statistical witness indistinguishability [BKP+24] suggests extending such a result to all of NP may be impossible. Zero-knowledge batch verification protocols are known for problems admitting non-interactive statistical zero-knowledge proofs [KRR+20, KRV21, MNRV24, KRV24] . Under cryptographic assumptions, computationally sound noninteractive batch arguments are known for all of NP [KPY19, CJJ21, CJJ22, DGKV22, WW22, KLVW23]; recent work has even constructed succinct interactive (classical) batch arguments for QMA [GJMG25] . In cryptography, the study of batch verification of NP statements has led to new constructions of succinct non-interactive arguments (SNARGs) [CJJ22, KVZ21] and non-interactive zero-knowledge arguments (NIZKs) [CW23] for more expressive classes and from weaker assumptions. Finally,[NR25] recently initiated a study of quantum witness indistinguishable proofs and showed that they are implied by quantum batch proofs. In this work, we study the batch verification problem for quantum Merlin-Arthur (QMA) proofsin the query and communication models. These models abstract computation to settings where techniques are available for proving strong lower bounds, yet which shed both conceptual and technical light on the corresponding Turing machine model. In the QMA query or black-box model, hereafter denoted by QMAdt, a quantum verifier (the resource-bounded mortal “Arthur”) wishes to evaluate a known function f : {−1, 1}n → {−1, 1} on an input x ∈ {−1, 1}n.1 He receives a witness consisting of w qubits from a prover (the all-powerful wizard “Merlin”), and is allowed to make q queries to x in quantum superposition. The protocol is correct if (1) whenever f (

FAQs

What does batch verification in QMA study?

It studies how the resources needed to verify m copies of a Boolean function f scale with m, measured via QMA query/communication complexity and the witness-query tradeoff.

How does approximate degree relate to the paper’s lower bounds?

The paper provides a general technique that derives lower bounds on the witness-query tradeoff for batch verification of f in terms of f’s approximate degree.

What is the main limitation on batching for the explicit DNF family?

For the constructed DNF family, any attempt to save even a constant factor in witness length leads to a large polynomial increase in query cost when batch verifying f.

Jul 16, 2026

Upload by Miles