{"id":"ce60522f-f25f-4562-8ee9-f826b41e2292","arxiv_id":"2611.16412","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":9.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves a general composition theorem for exact quantum query complexity, leading to improved separations: sensitivity vs exact quantum exponent 3/2 and randomized vs exact quantum nearly exponent 2.","lead":"The paper develops an exact quantum algorithm for composed Boolean functions that uses approximate inner evaluations with a correction step bounded by the outer function's degree. This improves prior composition bounds and yields near-optimal separations between sensitivity and exact quantum complexity, and between randomized and exact quantum complexity.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's verdict (ACCEPT, high confidence, medium correctness risk) aligns with my analysis. The weakest assumption identified (clean-phase outer algorithm) is standard and explicitly handled via factor-2 overhead. The paper provides detailed proofs, explicit constructions, and acknowledges its own limitations. I find no internal inconsistency or missing step that would warrant a different verdict.","tokens_in":38195,"tokens_out":7725,"duration_ms":60644,"concrete_test":"Reproduce Theorem 4.1's operator expansion for a concrete small case, e.g., f=AND_2 on n=2 bits (deg=2, Ef=2) and g=OR_2 on m=2 bits. Implement the truncated circuit as described (with error threshold 1/(1024·4)=1/4096) and verify by simulation or analysis that the return amplitude equals (-1)^{f∘g(x)} exactly for all 4 inputs. If the construction fails on any input, the interpolation argument in §4.4 would be invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After careful review, I find no unresolved load-bearing concern. The central composition bounds (Theorems 3.1 and 4.1) are supported by rigorous constructions that account for the clean-phase requirement (standard, with factor-2 overhead, explicitly noted in §2.1), the use of approximate inner evaluations, the exact algebraic correction, and the norm bounds. The recursive applications and separation results follow logically from these bounds. The AI statement is noted but does not affect correctness. The paper's own limitations (§12) discuss open improvements rather than gaps. I cannot identify a concrete technical flaw that would undermine the central claims.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"This paper proves a general composition theorem for exact quantum query complexity: for nonconstant total Boolean functions f (degree D) and g (on m bits), Q_E(f ∘ g) = O(m D + Q_E(f) Q_{1/(4D)}(g)). The algorithm combines approximate inner evaluations with an exact correction based on the outer function's multilinear expansion, where the correction cost is bounded by the degree D. This improves over the trivial O(Q_E(f) Q_E(g)) bound and extends prior work that only handled OR inner functions. The paper then applies the composition theorem to obtain tight exponential rates for recursive functions (e.g., recursive NAE achieves rate 3/√2), derives transfer principles that convert gadget-level conditions into universal exact-query bounds, and constructs explicit families achieving improved separations: sensitivity vs Q_E with exponent 3/2 (improving 1.1527) and randomized vs Q_E with exponent approaching 2 (improving 3/2). Analogous separations in quantum communication complexity are also given.","tokens_in":40200,"tokens_out":2087,"duration_ms":39015,"significance":"If the results are correct, they represent a substantial advance in exact quantum query complexity. The composition theorem is the first to exploit degree rather than exact query complexity for the correction cost, leading to optimal recursive rates for any gadget. The separations improve long-standing bounds in query and communication complexity. The transfer principles provide a clean criterion for universal bounds, unifying several known results. The proofs are rigorous and detailed, using established tools but delivering new algorithmic constructions.","major_comments":[{"comment":"The construction for implementing the truncated operator expansion assumes that each positive-order factor's dilation can be applied with cost 2m queries by reading the selected input block. However, the dilation matrix D(K_{u,k}) depends on K_{u,k}, which in turn depends on the error probability p_u and the state |r_u⟩ (see §4.2). The authors state that this table is fixed in advance and that controlled application is input-independent once the string u is known. This is correct in the query model, but the description could be clarified: the dilation for each possible u and k is precomputed, and the query to u is used to select the appropriate unitary. The cost analysis (2m per positive-order factor) is sound and standard. I find no issue here.","section":"§4.5, Eq. (4.14)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof that the return amplitude P_x(λ) equals H(b+λe) relies on the joint spectral decomposition of commuting reflections V_i(λ). Since the V_i(λ) act on disjoint registers and each is Hermitian, they indeed commute and share a simultaneous eigenbasis. The averaging over signs is then justified by the initial product state. This reasoning is correct and elegantly avoids analyzing the operator expansion directly.","section":"§4.4, Lemma 4.4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The recurrence T_d ≤ C (δ^k r^{d-k} + k T_k A^{d-k}) is derived from Theorem 4.1, but the constant C and the factor k in the second term need justification. From Theorem 4.1, the additive term is 12 Q_E(F_k) Q_{1/(4 deg(F_k))}(H_ℓ). Using Q_E(F_k)=T_k and deg(F_k)=δ^k, and the error reduction cost for H_ℓ is O(k A^ℓ) (since log(1/ε)=O(k) and Q(H_ℓ)=Θ(A^ℓ)), we get factor k from log(1/ε). The constant C can be chosen to absorb the O(k) factor and the constants from error reduction. This is valid and standard; the induction then handles the growth. The paper's analysis is sound.","section":"§6.1, Eq. (6.6)","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The Taylor expansion (3.3) uses ∂_S H(b) without factorial factors because H is multilinear. It might be helpful to explicitly note that ∂_S H(b) = Σ_{T⊇S} Ĥ(T) b^{T\\S}, which is indeed the coefficient without factorial. The current text says 'There are also no factorials, since a variable occurs at most once in each monomial.' This is clear enough.","section":"§3.2, Eq. (3.3)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The construction B_S is described as a tensor product of A_i (for i∉S) and Hadamard gates (for i∈S). However, the Hadamard gate on the answer qubit q_i produces the uniform superposition state, which gives Y_i = ±1 with equal probability. This matches the distribution needed in Lemma 3.2. The verification that P_S = ∏_{i∈S} Z_{q_i} provides the correct parity is correct. The query-by-query implementation is clearly explained.","section":"§3.3, proof of Lemma 3.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The computation of L uses the bound (1 + Σ w_k)^{T} ≤ e^{16 E_f √ε}. Since T = 2E_f, this is e^{2E_f ln(1+8√ε)} ≤ e^{2E_f * 8√ε} = e^{16 E_f √ε}. With ε = 1/(1024 E_f^2), √ε = 1/(32 E_f), so the exponent is 16/32 = 1/2. This is correct. However, the step 'using the uniform majorant from Lemma 4.3' implicitly assumes that the wk are the same for all positions, which is true as they depend only on ε. The sum over k≥1 wk ≤ 8√ε is from Lemma 4.3. The inequality (1+8√ε)^T ≤ exp(8√ε T) uses (1+x)≤e^x; 8√ε T = 8*(1/(32 E_f))*2E_f = 8/16 = 1/2. So L ≤ e^{1/2} < 2. This is correct.","section":"§4.5, line after Eq. (4.15)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The recurrence uses the factor k (from error reduction) multiplied by E_k A^{d-k}. The constant C is absolute. Later, in the induction (5.4), the factor d appears (since k ≈ β d). The analysis correctly accounts for the depth-dependent overhead.","section":"§5, Eq. (5.2)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The induction for the degree-dominated case uses the choice ℓ = ⌈ log(2Cd) / log(δ/A) ⌉ and shows u_d ≤ C_2 (d+1)^p + ½ u_{d-ℓ}. This is standard. The induction base is chosen large enough. The bound is correct.","section":"§6.1, last paragraph before §6.2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The claim that s(G_k) = N_k uses that each input bit is sensitive at zero. This holds because flipping any bit in any OR block changes that OR output, and F_k is fully sensitive at zero to changes in the outer bits. The reasoning is sound.","section":"§8, Eq. (8.6)","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"accept"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"This is a serious piece of work. The core result is a composition theorem for exact quantum query complexity that separates the cost of simulating the outer algorithm from the cost of correcting approximate inner evaluations. The degree-dependent error threshold (Theorem 4.1) is clever and yields a unified framework that determines the exact recursive rate for any fixed gadget. The payoffs are real: the sensitivity vs Q_E exponent moves from 1.1527 to 3/2, and the randomized vs Q_E exponent goes from 1.5 to nearly 2. The transfer principles cleanly convert these single-gadget gains into universal statements. The communication applications are a nice bonus.\n\nThe paper earns its length. The constructions are worked out in detail, the counting arguments are solid, and the authors are honest about what remains open. They explicitly flag the obstacle to replacing m by Q_E(g) in the correction cost (§12) and acknowledge the polylog overhead in some recursive bounds. They also give an open problem that would settle the tight complexity for recursive NAE. The AI statement is transparent and doesn't affect the science.\n\nMy only caveat is a disappointment rather than a flaw: the correction cost still reads full inner blocks rather than exploiting an exact inner algorithm. The authors know this and leave it as a conjecture. The paper also depends on [22] (Pednekar–Podder), an unpublished manuscript, but the authors provide their own derivation and do not rely on it for load-bearing claims. The clean-phase assumption is standard and the factor-2 overhead is accounted for.\n\nThis paper is for the query complexity community. It advances the state of the art and will be a reference for composition and separations. It deserves a serious referee and, after a normal review, should be accepted.","headline":"Strong paper: general composition theorem for exact quantum query complexity, improved separations, rigorous proofs. Soft spots are openly discussed and minor.","tokens_in":38876,"tokens_out":1281,"duration_ms":11317},"pith_extraction":{"msc":["68Q12","68Q17","81P68"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"A general composition theorem for exact quantum query complexity, showing that approximate inner evaluations with exact correction yield improved bounds, recursive rate equals max(degree, adversary), and new separations from sensitivity…","keywords":["exact quantum query complexity","composition of Boolean functions","approximate inner evaluation","exact correction","recursive functions","degree","adversary bound","transfer principle"],"falsifier":"Produce a total Boolean function g for which Q_{1/(4 deg(f))}(g) is much larger than the bound used in the paper, or find a pair (f,g) where the inequality Q_E(f∘g) ≤ 6m deg(f) + 804 Q_E(f) Q_{1/(4D)}(g) fails (with the constant 804). This would require a counterexample constructed from explicit algorithms.","tokens_in":41701,"feed_emoji":"🔬","tokens_out":2450,"duration_ms":35193,"temperature":0.7,"pith_summary":"This paper establishes that the exact quantum query complexity of a composed Boolean function $f \\circ g$ can be bounded by $O(m \\deg(f) + Q_E(f) Q_{1/(4 \\deg(f))}(g))$, where the first term pays for reading a few inner blocks to correct errors, and the second pays for simulating the outer algorithm with approximate inner queries. The authors develop two constructions: one using a Taylor expansion in the biases of approximate inner algorithms, and one using an operator interpolation whose return amplitude is a polynomial of degree at most $\\deg(f)$. This leads to exact algorithms for recursive functions whose exponential growth rate is exactly $\\max\\{\\deg(h), \\operatorname{Adv}^{\\pm}(h)\\}$. Using these tools, the authors derive transfer principles that convert gadget-level inequalities into universal exact-query bounds, and construct explicit families: one separating sensitivity (and block sensitivity) from exact quantum queries with exponent $3/2$, improving the previous $1.1527\\ldots$ exponent, and another separating randomized query complexity from exact quantum queries with exponent $2 - o(1)$, improving the previous $3/2$ exponent. The results apply also to quantum communication via AND lifts and inner-product lifts.","feed_headline":"Exact quantum composition bound improves separations","feed_subtitle":"New algorithm evaluates f∘g by combining approximate inner queries with exact correction, achieving exponent 3/2 for sensitivity and 2 −…","key_machinery":"The main machinery is a composition algorithm that first uses an approximate quantum algorithm for the inner function $g$ with error $\\varepsilon = 1/(4\\deg(f))$, then corrects the resulting bias coherently using an exact multilinear expansión of the outer function $f$. The correction reads at most $\\deg(f)$ inner blocs entirely (cost $O(m \\deg(f))$) and combines them via a suposición with input-independent weights. A second construction interpolates the inner reflection operators and truncates the Taylor series at order $\\deg(f)$; the return amplitude is exactly $H(b+\\lambda(z-b)$, a polynomial of degree $\\deg(f)$. Both methods use exact amplitude amplification to convert the known magnitude amplitude into the exact phase.","core_discovery":"The paper proves that for any nonconstant total Boolean functions $f$ on $n$ bits and $g$ on $m$ bits, $Q_E(f \\circ g) = O(m \\deg(f) + Q_E(f) Q_{1/(4 \\deg(f))}(g))$, and this allows exponential exact quantum improvements for recursive functions. For a fixed nonconstant $h$, the exact quantum query complexity of $h^{\\circ k}$ grows as $\\max\\{\\deg(h), \\operatorname{Adv}^{\\pm}(h)\\}^k$ up to subexponential factors, giving a composition limit. This is used to prove transfer principles: a universal bound $L(F) = O(Q_E(F)^\\alpha)$ for a composable measure $L$ holds iff $L(f) \\leq \\max\\{\\deg(f), \\operatorname{Adv}^{\\pm}(f)\\}^\\alpha$ for all $f$. The paper then constructs explicit total Boolean functions that achieve improved separations: $s = \\operatorname{bs} = \\operatorname{fbs} \\geq Q_E^{3/2 - o(1)}$ (exponent $3/2$), and $R \\geq Q_E^{2 - o(1)$ (near quadratic randomized-exact gap). These separations carry over to quantum communication complexity.","pith_inferences":["The bound $Q_E(f \\circ g) = O(m \\deg(f) + Q_E(f) Q_{1/(4\\deg(f))}(g))$ suggests that the naive multiplicative simulation $Q_E(f \\circ g) = \\Theta(Q_E(f)Q_E(g))$ can be broken whenever $\\deg(f)$ is small compared to $Q_E(f)$ and $g$ has efficient approximate algorithms. This opens the door to many non-multiplicative compositions.","The transfer principles imply that proving a universal quadratic bound $Q_E(F) = O(R(F)^2)$ for all total $F$ would be equivalent to proving $\\max\\{\\deg(f), \\operatorname{Adv}^{\\pm}(f)\\} = O(R(f))$ for all $f$, which is already known up to constants; thus the quadratic bound might hold universally, but the proof would need to avoid the fixed-gadget restriction.","The cheat-sheet gadget together with the recursive exact algorithm provides a template for constructing total functions with near-quadratic randomized-exact quantum gap. The remaining polylogarithmic loss might be removable by a more direct exact correction that does not read entire inner blocks, perhaps using an exact inner algorithm instead of approximate one."],"forward_implications":["For any recursive function $h^{\\circ k}$, the exact quantum query complexity is $\\tilde O_h(R(h^{\\circ k})^2)$, so bounded-error randomized query complexity gives a quadratic upper bound on exact quantum query complexity for these iterated functions.","The transfer principle reduces many universal exact-query lower bound problems to checking a finite condition on individual gadgets; for example, $s(F) = O(Q_E(F)^\\alpha)$ for all $F$ iff $\\operatorname{fbs}(f) \\leq \\max\\{\\deg(f), \\operatorname{Adv}^{\\pm}(f)\\}^\\alpha$ for all $f$.","The exponent-$3/2$ separation between sensitivity and exact quantum queries (and the nearly quadratic separation between randomized and exact quantum queries) are the strongest known, and the methods suggest possible routes to further improvements.","In quantum communication complexity, the same techniques yield analogous separations: $R^{cc}_{1/3}(HG_k) \\geq (Q^{cc}_E(HG_k))^{3/2 - o(1)}$ and $R^{cc}_{1/3} \\geq (Q^{cc}_E)^{2 - o(1)}$ for appropriate families."],"supporting_citations":[{"why":"Provides the polynomial method and the lower bound Q_E(f) >= deg(f)/2.","marker":"[7]"},{"why":"Characterize bounded-error quantum query complexity via the general adversary bound Adv^{pm}, including its composition.","marker":"[19, 24]"},{"why":"Previous work on exact composition for OR inner function, which the present paper generalizes to arbitrary inner functions.","marker":"[22]"},{"why":"Supplies composition laws for degree and degree-dependent error thresholds used in Section 4.","marker":"[26]"},{"why":"Provides exact amplitude amplification used to convert the known-magnitude amplitude into the exact phase.","marker":"[9]"},{"why":"Supply cheat-sheet construction and sabotage complexity lower bounds used for the randomized-exact separation.","marker":"[1, 8]"},{"why":"Provide quantum query-to-communication simulation and randomized lifting theorems used in the communication separation.","marker":"[12, 14]"}],"fun_headline_variants":["Exact quantum composition bound tightens sensitivity gap","Quantum algorithm for composed functions achieves exponent 3/2","Novel composition limit boosts exact quantum separations","Exact quantum query complexity gets exponent-2 random gap"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The construction assumes that the outer function f has an exact quantum algorithm that returns a clean phase, which can always be achieved with a factor-2 overhead, and that the inner algorithm g can be run with error probability at most 1/(4 deg(f)).","fun_headline_variants_meta":{"raw":{"variants":["Exact quantum composition bound tightens sensitivity gap","Quantum algorithm for composed functions achieves exponent 3/2","Novel composition limit boosts exact quantum separations","Exact quantum query complexity gets exponent-2 random gap"]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":0.000226,"raw_usage":{"cost":0.000226408,"is_byok":false,"cost_details":{"upstream_inference_cost":0.000226408,"upstream_inference_prompt_cost":0.000133168,"upstream_inference_completions_cost":9.324e-05},"total_tokens":1489,"prompt_tokens":1156,"completion_tokens":333,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":269}},"tokens_in":1156,"tokens_out":333,"cost_source":"openrouter_usage","duration_ms":4820,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":269,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T15:11:44.178699+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"Produce a total Boolean function g for which Q_{1/(4 deg(f))}(g) is much larger than the bound used in the paper, or find a pair (f,g) where the inequality Q_E(f∘g) ≤ 6m deg(f) + 804 Q_E(f) Q_{1/(4D)}(g) fails (with the constant 804). This would require a counterexample constructed from explicit algorithms.","supporting_citations":[{"cited_title":"Quantum Lower Bounds by Polynomials","cited_arxiv_id":"quant-ph/9802049","evidence_quote":"Provides the polynomial method and the lower bound Q_E(f) >= deg(f)/2."},{"cited_title":"Properties and applications of boolean function composition","cited_arxiv_id":null,"evidence_quote":"Supplies composition laws for degree and degree-dependent error thresholds used in Section 4."},{"cited_title":"Quantum Amplitude Amplification and Estimation","cited_arxiv_id":"quant-ph/0005055","evidence_quote":"Provides exact amplitude amplification used to convert the known-magnitude amplitude into the exact phase."}],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}