Pith. sign in

REVIEW 5 minor 42 references

QMA Lower Bounds for Batch Verification via Approximate Degree

T0 review · 0 major / 5 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Saving even a constant factor of witness length when batch-verifying certain DNFs forces a polynomial blow-up in QMA queries.

desk verdict Clean dual-polynomial technique that turns ordinary approximate degree into QMA batch tradeoffs and improves concrete lower bounds for SURJ and kED. read the letter →

arxiv 2607.08888 v1 pith:5SPLK26A submitted 2026-07-09 cs.CC

Mark Bun , Mandar Juvekar , Samuel King This is my paper · ORCID
classification cs.CC MSC 68Q1268Q1703D15
keywords QMAquerycomplexitybatchverificationapproximatedegreeSBQPdualselementdistinctnesssurjectivitypatternmatrixwitness-querytradeoff
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies how much one can compress the quantum witnesses needed to verify m independent copies of a Boolean function f. The baseline strategy simply concatenates m individual witnesses and uses Grover search, costing O(m log n) qubits and O(sqrt(m)) queries for constant-width DNFs. The authors prove that any protocol that trims the witness length by even a constant factor must pay a large polynomial increase in queries. They obtain the tradeoff by showing that high approximate degree of f forces high-degree SBQP approximations of the batch function AND_m o f^m; those approximations in turn lower-bound QMA query cost after Marriott–Watrous amplification. The same technique yields improved QMA lower bounds for the two-level AND-OR tree, surjectivity and k-element distinctness, and the bounds lift to the communication model via a pattern-matrix argument.

What carries the argument

Relaxed SBQP duals: dual polynomials that are well-correlated with the batch function, orthogonal to low-degree monomials, and place only tiny mass on misclassified true inputs. They are built by composing a one-sided dual for AND with an approximate-degree dual for f and Sherstov’s multilinear polynomial p_k, then shown to rule out low-degree SBQP approximations.

What would settle it

Exhibit any QMA protocol for the explicit DNF batch problem that uses witness length o(m log n) yet only O(sqrt(m) polylog n) queries, or produce a low-degree SBQP approximation that contradicts the claimed dual.

Watch

Extended reading notes

Core claim

If the approximate degree of f to error 1-1/m exceeds d, then every QMA query protocol for the batch function AND_m o f^m that uses only O(m) qubits of witness must make Omega(d sqrt(m/w)) queries. For an explicit family of constant-width polynomial-size DNFs this implies that beating the baseline witness length by any constant factor forces the query cost to jump from O(sqrt(m)) to nearly linear in n.

Load-bearing premise

The construction assumes that the mass the dual places on true inputs it misclassifies stays small enough; if that mass exceeds the allowed threshold the dual ceases to certify the degree lower bound.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies batch verification of Boolean functions in the QMA query and communication models. It introduces a general technique that converts approximate-degree lower bounds for a base function f into witness-query tradeoffs for AND_m ◦ f^m. The key technical device is a relaxed (M, ε, d)-SBQP dual (Definition 3.1 / Lemma 3.2) constructed in Theorem 3.5 by combining a one-sided dual for AND (Theorem 3.3), a dual for f, and Sherstov’s multilinear polynomial p_k (Lemma 3.4). Corollaries 3.6–3.7 and the Marriott–Watrous reduction (Lemma 4.1) then yield concrete QMA_dt tradeoffs (Theorems 4.2, 4.4). These are applied to obtain new lower bounds for an explicit constant-width DNF family (Corollary 4.3), the two-level AND-OR tree, SURJ, and kED (Theorem 4.5). The same duals lift via a pattern-matrix argument (Section 5) to matching QMA_cc lower bounds.

Significance. The work supplies the first direct, general connection between ordinary approximate degree and QMA_dt batch-verification cost, bypassing the earlier need for one-sided vanishing-error approximate degree. The resulting tradeoffs are strong enough to show that even a constant-factor saving in witness length for an explicit DNF forces a polynomial blow-up in queries, and they improve the best-known QMA_dt bounds for SURJ (to Õ(n^{3/7})) and kED. The pattern-matrix lift is clean and immediately yields communication analogues. The dual construction is fully rigorous and self-contained once the literature duals for AND and f are taken as black boxes; no machine-checked proofs or code are supplied, but the mathematics is standard and verifiable by hand.

minor comments (5)
  1. In the abstract and Theorem 1.3 the phrase “read-once CNF formulas” appears, yet the body only treats the two-level AND-OR tree (AND_m ◦ OR_n). Align the terminology or add a short remark clarifying the relationship.
  2. After Equation (3) the mass bound relies on the one-sidedness of the AND dual and the non-negativity of p_k. A one-sentence reminder of these two facts would make the calculation easier to follow on a first reading.
  3. In Corollary 4.3 the upper-bound protocol uses Grover search over m terms of width k; the query cost is stated as O(k √m). A parenthetical citation to the standard multi-item Grover analysis (e.g., Høyer–Mosca–de Wolf) would be helpful.
  4. Section 5.2, Lemma 5.2: the quantity Q is defined with a logarithm of a ratio involving the spectral norm; a brief remark that the same argument works with the trace norm (via the factorization identity already recalled) would clarify the matrix-analytic ingredients.
  5. A few typographical inconsistencies remain: “naïve” vs. “naive”, occasional missing spaces around ◦, and the arXiv date line still reads “July 9, 2026”.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: independent dual construction from external approximate-degree duals yields QMA lower bounds by standard LP duality and Marriott-Watrous.

full rationale

The paper is pure complexity-theoretic lower-bound mathematics. Approximate-degree duals for AND (Theorem 3.3, from Buhrman et al.) and for the base functions f (from Sherstov, Bun-Thaler, Ambainis, etc.) are imported as external black-box facts. The authors construct a new relaxed SBQP dual for the composed function AND_m ◦ f^m (Theorem 3.5) by combining those duals with Sherstov’s multilinear polynomial p_k; the correlation, pure-high-degree, and almost-one-sided-error properties are proved by direct calculation (Eqs. (1)–(3) and the subsequent mass bound). This dual is then fed into ordinary LP duality (Lemma 3.2) and the standard Marriott-Watrous amplification (Lemma 4.1) to obtain the claimed QMA_dt trade-offs; the pattern-matrix lift (Section 5) is likewise a standard adaptation. No parameter is fitted to data, no uniqueness theorem is imported from the authors’ own prior work to force the result, and the target QMA complexity is never used as an input to the dual construction. The derivation is therefore self-contained against external mathematical benchmarks and exhibits no circular reduction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The argument rests only on standard facts of approximate degree, dual polynomials, Marriott-Watrous amplification, and the pattern-matrix method; no free parameters or new physical entities are introduced. The sole paper-specific invention is the relaxed SBQP dual, which is an auxiliary linear-programming object with no independent existence outside the proof.

assumptions (4)
  • standard math ε-approximate degree dual characterization (Theorem 2.1): existence of a pure-high-degree, unit-ℓ1 dual with correlation ≥ε
    Invoked throughout §3 to obtain duals ψ for AND and φ for f; classical result of Sherstov/Bun-Thaler.
  • standard math One-sided approximate degree of AND_m is Θ(√(m log(1/γ))) (Theorem 3.3)
    Used to supply the outer dual ψ; follows from Buhrman et al. plus a short one-sidedness argument given in the text.
  • standard math Marriott-Watrous in-place amplification reduces QMA error to 2^{-O(w)} at O(qw) query cost (Theorem 2.3)
    Converts any QMA protocol into an SBQP approximation (Lemma 4.1); classical result.
  • standard math Sherstov’s multilinear polynomial p_k and its expectation bound under product distributions (Lemma 3.4)
    Controls the mass of the composed dual on misclassified true inputs; taken from Sherstov 2012.
invented entities (1)
  • relaxed (M,ε,d)-SBQP dual
    purpose: A sufficient dual witness that rules out low-degree (M,ε)-SBQP approximations while being easier to construct than the exact LP dual
    Defined in Lemma 3.2 and used as the main technical object of §3; purely auxiliary, no claim of independent existence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of QMA Lower Bounds for Batch Verification via Approximate Degree." pith.science (2026). https://pith.science/paper/5SPLK26A

@misc{pith2026260708888,
  author       = {Pith},
  title        = {Pith review of: QMA Lower Bounds for Batch Verification via Approximate Degree},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5SPLK26A}},
  note         = {Machine review of arXiv:2607.08888}
}
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 1 linked inside Pith

  1. [1]

    Impossibility of succinct quantum proofs for collision-freeness

    Scott Aaronson. Impossibility of succinct quantum proofs for collision-freeness. Quantum Info. Comput. , 12(1–2):21–28, 2012

    2012

  2. [2]

    Quantum lower bounds for approximate counting via Laurent polynomials

    Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum lower bounds for approximate counting via Laurent polynomials. In 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbr \" u cken, Germany (Virtual Conference) , 2020

    2020

  3. [3]

    Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range

    Andris Ambainis. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory Comput. , 1(1):37--46, 2005

    2005

  4. [4]

    Quantum lower bounds for the collision and the element distinctness problems

    Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. J. ACM , 51(4):595--605, 2004

    2004

  5. [5]

    Quantum lower bounds by polynomials

    Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM) , 48(4):778--797, 2001

    2001

  6. [6]

    Bounds for small-error and zero-error quantum algorithms

    Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999 , 1999

    1999

  7. [7]

    Batch proofs are statistically hiding

    Nir Bitansky, Chethan Kamath, Omer Paneth, Ron D Rothblum, and Prashant Nalini Vasudevan. Batch proofs are statistically hiding. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 435--443, 2024

    2024

  8. [8]

    The polynomial method strikes back: Tight quantum query bounds via dual polynomials

    Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. Theory Comput. , 16:1--71, 2020

    2020

Show all 42 references
  1. [9]

    Dual lower bounds for approximate degree and M arkov-- B ernstein inequalities

    Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and M arkov-- B ernstein inequalities. Inf. Comput. , 243:2--25, 2015

    2015

  2. [10]

    Hardness amplification and the approximate degree of constant-depth circuits

    Mark Bun and Justin Thaler. Hardness amplification and the approximate degree of constant-depth circuits. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I , 2015

    2015

  3. [11]

    The large-error approximate degree of AC^0

    Mark Bun and Justin Thaler. The large-error approximate degree of AC^0 . Theory of computing , 2018

    2018

  4. [12]

    Approximate degree in classical and quantum computing

    Mark Bun and Justin Thaler. Approximate degree in classical and quantum computing. Foundations and Trends in Theoretical Computer Science , 15(3--4):229--423, 2022

    2022

  5. [13]

    Non-interactive batch arguments for NP from standard assumptions

    Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. Non-interactive batch arguments for NP from standard assumptions. In Annual International Cryptology Conference , 2021

    2021

  6. [14]

    Snargs for P from LWE

    Arka Rai Choudhuri, Abhihsek Jain, and Zhengzhong Jin. Snargs for P from LWE . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , 2022

    2021

  7. [15]

    Non-interactive zero-knowledge from non-interactive batch arguments

    Jeffrey Champion and David J Wu. Non-interactive zero-knowledge from non-interactive batch arguments. In Annual International Cryptology Conference , pages 38--71. Springer, 2023

    2023

  8. [16]

    Rate-1 non-interactive arguments for batch- NP and applications

    Lalita Devadas, Rishab Goyal, Yael Kalai, and Vinod Vaikuntanathan. Rate-1 non-interactive arguments for batch- NP and applications. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , 2022

    2022

  9. [17]

    Quantum proofs of proximity

    Marcel Dall'Agnol, Tom Gur, Subhayan Moulik, and Justin Thaler. Quantum proofs of proximity. Quantum , 6:834, 2022

    2022

  10. [18]

    Succinct arguments for batch qma and friends under 8 rounds

    Rishab Goyal, Aditya Jain, and Shashwatha Mitra GB. Succinct arguments for batch qma and friends under 8 rounds. In Annual International Cryptology Conference , 2025

    2025

  11. [19]

    Sherstov

    Dmitry Gavinsky and Alexander A. Sherstov. A separation of NP and coNP in multiparty communication complexity. Theory Comput. , 6(1):227--245, 2010

    2010

  12. [20]

    Quantum search on bounded-error inputs

    Peter H yer, Michele Mosca, and Ronald de Wolf. Quantum search on bounded-error inputs. In International Colloquium on Automata, Languages, and Programming , 2003

    2003

  13. [21]

    On A rthur M erlin games in communication complexity

    Hartmut Klauck. On A rthur M erlin games in communication complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011 , 2011

    2011

  14. [22]

    Boosting batch arguments and ram delegation

    Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Daniel Wichs. Boosting batch arguments and ram delegation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1545--1552, 2023

    2023

  15. [23]

    How to delegate computations publicly

    Yael Tauman Kalai, Omer Paneth, and Lisa Yang. How to delegate computations publicly. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages 1115--1124, 2019

    2019

  16. [24]

    Batch verification for statistical zero knowledge proofs

    Inbar Kaslasi, Guy N Rothblum, Ron D Rothblum, Adam Sealfon, and Prashant Nalini Vasudevan. Batch verification for statistical zero knowledge proofs. In Theory of Cryptography Conference , 2020

    2020

  17. [25]

    Public-coin statistical zero-knowledge batch verification against malicious verifiers

    Inbar Kaslasi, Ron D Rothblum, and Prashant Nalini Vasudevanr. Public-coin statistical zero-knowledge batch verification against malicious verifiers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages 219--246. Springer, 2021

    2021

  18. [26]

    Doubly-efficient batch verification in statistical zero-knowledge

    Or Keret, Ron D Rothblum, and Prashant Nalini Vasudevan. Doubly-efficient batch verification in statistical zero-knowledge. In Theory of Cryptography Conference , 2024

    2024

  19. [27]

    Somewhere statistical soundness, post-quantum security, and SNARGs

    Yael Tauman Kalai, Vinod Vaikuntanathan, and Rachel Yun Zhang. Somewhere statistical soundness, post-quantum security, and SNARGs . In Theory of Cryptography Conference , 2021

    2021

  20. [28]

    Lower bounds in communication complexity based on factorization norms

    Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing , 2007

    2007

  21. [29]

    Strong batching for non-interactive statistical zero-knowledge

    Changrui Mu, Shafik Nassar, Ron D Rothblum, and Prashant Nalini Vasudevan. Strong batching for non-interactive statistical zero-knowledge. In Annual International Conference on the Theory and Applications of Cryptographic Techniques , 2024

    2024

  22. [30]

    Mande, Justin Thaler, and Shuchen Zhu

    Nikhil S. Mande, Justin Thaler, and Shuchen Zhu. Improved approximate degree bounds for k-distinctness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, Riga, Latvia, June 9-12, 2020 , 2020

    2020

  23. [31]

    Quantum A rthur- M erlin games

    Chris Marriott and John Watrous. Quantum A rthur- M erlin games. Comput. Complex. , 14(2):122--152, 2005

    2005

  24. [32]

    Quantum statistical witness indistinguishability

    Shafik Nassar and Ronak Ramachandran. Quantum statistical witness indistinguishability. Technical Report arXiv:2509.01945, 2025

    2025 arXiv

  25. [33]

    Batch verification and proofs of proximity with polylog overhead

    Guy N Rothblum and Ron D Rothblum. Batch verification and proofs of proximity with polylog overhead. In Theory of Cryptography Conference , 2020

    2020

  26. [34]

    Constant-round interactive proofs for delegating computation

    Omer Reingold, Guy N Rothblum, and Ron D Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 49--62, 2016

    2016

  27. [35]

    Rothblum, and Ron D

    Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Efficient batch verification for UP . In 33rd Computational Complexity Conference (CCC 2018) , 2018

    2018

  28. [36]

    On the power of quantum proofs

    Ran Raz and Amir Shpilka. On the power of quantum proofs. In 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA , 2004

    2004

  29. [37]

    Sherstov

    Alexander A. Sherstov. The pattern matrix method. SIAM J. Comput. , 40(6):1969--2000, 2011

    1969

  30. [38]

    Sherstov

    Alexander A. Sherstov. Strong direct product theorems for quantum communication and query complexity. SIAM J. Comput. , 41(5):1122--1165, 2012

    2012

  31. [39]

    Sherstov

    Alexander A. Sherstov. Approximating the AND-OR tree. Theory Comput. , 9:653--663, 2013

    2013

  32. [40]

    Sherstov

    Alexander A. Sherstov. The approximate degree of DNF and CNF formulas. SIAM J. Comput. , 54(3):702--774, 2025

    2025

  33. [41]

    Sherstov and Justin Thaler

    Alexander A. Sherstov and Justin Thaler. Vanishing-error approximate degree and QMA complexity. Chicago Journal of Theoretical Computer Science , 2023(3), 2023

    2023

  34. [42]

    Batch arguments for NP and more from standard bilinear group assumptions

    Brent Waters and David J Wu. Batch arguments for NP and more from standard bilinear group assumptions. In Annual International Cryptology Conference , pages 433--463, 2022

    2022

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.