{"id":"6a21618f-d245-4229-9fa4-6e741ffecb83","arxiv_id":"2607.08888","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Approximate degree of f yields QMA witness-query tradeoffs for AND_m ◦ f^m, giving new lower bounds for surjectivity, k-element distinctness, and DNF batch verification.","lead":"The paper shows that batch-verifying m copies of a Boolean function in quantum Merlin-Arthur query complexity inherits strong witness-query tradeoffs from the approximate degree of the base function. Even constant-factor savings on witness length for certain DNFs force a large polynomial blowup in queries, with matching communication lifts.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the only non-routine step—the almost-one-sided mass calculation after Eq. (3)—and that step checks out under the stated parameter regimes. All other ingredients (dual of AND, Sherstov’s p_k, Marriott–Watrous amplification, pattern-matrix spectral-norm bound) are standard and applied without circularity. Consequently the strongest claim (Theorem 1.2 / Corollaries 3.6–3.7) stands, the concrete lower bounds of Theorem 1.3 follow, and the ACCEPT verdict with high confidence requires no adjustment.","tokens_in":25941,"tokens_out":444,"duration_ms":4413,"concrete_test":"Independently recompute the mass bound after Eq. (3) for the concrete parameters of Corollary 3.6 (c=1, η=1/m, k=⌊(δ_AND/2)√(m log(1/γ))⌋ even) and verify that it remains ≤ ε/M for all m≥100; if the inequality fails for any such m the dual is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The dual construction of Theorem 3.5 correctly inherits almost-one-sided error from the one-sided dual of AND (Theorem 3.3) and the error bound of p_k (Lemma 3.4). After Eq. (3) the mass on misclassified true inputs is bounded by η^{k+1}/(2(1-η)^m) binom(m,k+1) which is forced ≤ ε/M by the parameter choices of Corollaries 3.6–3.7; the subsequent Marriott–Watrous reduction (Lemma 4.1) and pattern-matrix lift are standard. No hidden assumption or calculation gap appears that would collapse the degree lower bound.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":26133,"tokens_out":881,"duration_ms":6993,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"A few typographical inconsistencies remain: “naïve” vs. “naive”, occasional missing spaces around ◦, and the arXiv date line still reads “July 9, 2026”.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a clean, technically solid contribution that sits comfortably in the approximate-degree / quantum-query literature. No novelty or citation concerns arose. I see no reason to delay acceptance."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The real news is a reusable dual construction that converts ordinary (two-sided) approximate-degree lower bounds into witness-query tradeoffs for batch-verifying AND_m ◦ f^m in QMA_dt, then lifts them to communication. Prior SBQP arguments needed one-sided or vanishing-error degree, which fail for AND-OR trees, k-element distinctness and surjectivity; this paper works directly with relaxed SBQP duals and therefore gets the first constant-factor witness hardness for DNF batching plus the improved bounds QMA_dt(SURJ_n)=Õ(n^{3/7}) and QMA_dt(kED_n)=Õ(n^{(3k-1)/(7k-1)}).\n\nWhat they do well is elementary and careful. Theorem 3.5 builds the dual for the composed function by combining the known one-sided dual of AND, a dual for f, and Sherstov’s multilinear p_k; the correlation, pure high degree and almost-one-sided mass are verified by direct calculation. Corollaries 3.6–3.7 and the Marriott–Watrous reduction (Lemma 4.1) then give the clean tradeoffs, and the pattern-matrix lift is standard. The math is self-contained once the external duals are plugged in; no free parameters or circularity.\n\nSoft spots are minor and already flagged by the authors. The almost-one-sided mass bound after Eq. (3) relies on the parameter choices that keep η^{k+1}/(2(1-η)^m) binom(m,k+1) ≤ ε/M; if those choices are violated the dual fails, but the corollaries stay inside the safe regime. The concrete exponents are still not tight, and the open questions (tightness of the tradeoff, starting from quantum query rather than approximate degree) are honest. Citation pattern is appropriate; they correctly credit Sherstov–Thaler, Bun–Thaler, etc.\n\nThis is for people who work on quantum query/communication lower bounds or batch verification. It deserves a serious referee and should be accepted after ordinary polishing. I would bring it to reading group and expect to cite the dual technique.","headline":"Clean dual-polynomial technique that turns ordinary approximate degree into QMA batch tradeoffs and improves concrete lower bounds for SURJ and kED.","tokens_in":26755,"tokens_out":562,"would_cite":true,"duration_ms":7032,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q17","03D15"],"pacs":[],"model":"grok-4.5","headline":"Saving even a constant factor of witness length when batch-verifying certain DNFs forces a polynomial blow-up in QMA queries.","keywords":["QMA query complexity","batch verification","approximate degree","SBQP duals","element distinctness","surjectivity","pattern matrix","witness-query tradeoff"],"falsifier":"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.","tokens_in":26860,"feed_emoji":"⚛️","tokens_out":684,"duration_ms":7528,"temperature":0.7,"pith_summary":"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.","feed_headline":"Shorter QMA witnesses force far more queries for batch DNFs","feed_subtitle":"Constant-factor witness savings on explicit DNFs demand nearly linear query cost","key_machinery":"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.","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Approximate degree forces Omega-query blowup for short QMA batch witnesses","Constant-factor shorter QMA witnesses demand nearly linear queries on DNFs","Batch DNF QMA: short witnesses require nearly linear query cost via approx degree","QMA batch verification of DNFs: witness savings force Omega(sqrt m) to linear queries","Approx-degree lower bound: O(m)-qubit QMA batch DNFs jump to nearly linear queries"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Approximate degree forces Omega-query blowup for short QMA batch witnesses","Constant-factor shorter QMA witnesses demand nearly linear queries on DNFs","Batch DNF QMA: short witnesses require nearly linear query cost via approx degree","QMA batch verification of DNFs: witness savings force Omega(sqrt m) to linear queries","Approx-degree lower bound: O(m)-qubit QMA batch DNFs jump to nearly linear queries"]},"model":"grok-4.5","effort":"low","cost_usd":0.001706,"raw_usage":{"total_tokens":821,"prompt_tokens":709,"num_sources_used":0,"completion_tokens":112,"cost_in_usd_ticks":17060000,"prompt_tokens_details":{"text_tokens":709,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":0,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":709,"tokens_out":112,"duration_ms":1783,"temperature":1.0,"reasoning_tokens":0,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T06:00:24.394351+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}