{"id":"8786fe2f-40e2-4cc0-a93e-9b0fa23ebd51","arxiv_id":"2607.08517","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A matrix-discrepancy argument proves tight one-way quantum lower bounds for collision finding (Ω(N^{1/4})) and for streaming triangle finding (Ω(√Δ_V)) where Boolean-Hidden-Matching reductions fail.","lead":"This paper gives a matrix-discrepancy method that proves one-way quantum communication lower bounds for search problems with many valid outputs. It yields the first tight Ω(N^{1/4}) quantum bound for bipartite collision finding and an Ω(√Δ_V) quantum streaming lower bound for triangle finding in a natural parameter regime.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript’s central claims (Theorems 1.1 and 1.2) rest on a clean reduction of search success probability to the spectral norm of a centered packed operator, followed by standard non-commutative concentration. The reader correctly identified the packing step as the modeling hinge, but that hinge is fully discharged: the POVM axioms plus the Bob-side validity indicators force precisely the hypotheses used by the discrepancy lemmas. No protocol can evade those hypotheses while remaining a valid one-way quantum protocol. The proofs are self-contained, the parameter regimes are stated carefully, and the classical recovery for triangle finding is an independent sanity check. Consequently the reader’s ACCEPT / high-confidence verdict stands; no adjustment is warranted.","tokens_in":22862,"tokens_out":546,"duration_ms":5379,"concrete_test":"Independently re-derive the collision packing after Definition 2.4 and the application of Lemmas 3.1–3.2 in §3.2: verify that every one-way protocol yields operators satisfying P_{i,j} ⪰ 0, P_{i,j} ⪯ I/√N and ∑P_{i,j} ⪯ I, and that the random-bipartition + bucket-norm argument produces the claimed O(√((k log N)/√N)) bound on E∥G_x∥. If the packing hypotheses hold and the numerical bound matches (7), the central claim is secure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest-assumption concern (that some POVM packing might evade the matrix-Khintchine/Chernoff bounds while still obeying POVM normalization) does not land as a real gap. After Bob-side validity is absorbed, every protocol induces a packing satisfying exactly the hypotheses of Lemmas 3.1–3.2 (collision) and 4.4–4.6 (triangle): P_ω ⪰ 0, ∑P_ω ⪯ I, and the pointwise bounds P_{i,j} ⪯ I/√N or P_{x,i,z,y} ⪯ I/s. The subsequent discrepancy estimates therefore apply to every admissible packing; there is no residual freedom for a protocol to produce a packing whose grouped norms escape those bounds. The reduction of success probability to E∥H_a∥ (or E∥G_{F,A}∥) is standard and correctly justified by Tr(ρH) ≤ ∥H∥. Residual risk is ordinary human-proof error, not a conceptual hole.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper develops a matrix-discrepancy method for one-way quantum communication lower bounds on search relations. Bob's POVM is converted into a PSD packing by absorbing Bob-side validity factors; after subtracting the trivial baseline, the success probability is controlled by the expected operator norm of a centered random matrix sum under packing constraints, which is bounded via noncommutative Khintchine and matrix concentration. The method yields two applications: a tight Ω(N^{1/4}) one-way quantum lower bound for bipartite collision finding ColFind_{N,M} when M>N (Theorem 1.1), improving the prior Ω(N^{1/12}) bound, and an Ω(√Δ_V) one-pass quantum streaming space lower bound for triangle finding on a hard family with m edges, T=Θ(m), Δ_E=O(1) and 1≤Δ_V≤m^{2/3} (Theorem 1.2), matching the classical upper bound of Jayaram–Kallaugher up to logs and recovering the classical Kallaugher–Price lower bound without Boolean Hidden Matching.","tokens_in":23125,"tokens_out":804,"duration_ms":7150,"significance":"The contribution is substantial. Search problems with many valid outputs have resisted standard quantum lower-bound techniques; the measurement-discrepancy framework gives a direct, packing-based route that applies uniformly to both applications. Closing the quantum gap for collision finding to the birthday-paradox upper bound, and obtaining the first nontrivial quantum streaming lower bound that recovers the classical √Δ_V dependence in a regime where Boolean Hidden Matching is unavailable, are clear advances. The proofs are fully written from first principles (PSD packing extraction, centering, decoupling, matrix Khintchine/Chernoff), and the method also recovers a known classical lower bound by an independent argument. Residual risk is ordinary human-proof error rather than a conceptual hole.","major_comments":[],"minor_comments":[{"comment":"In the technical overview and in §3.2 the packing is written both as ∑P_ω ⪯ I and, in one place, with a ⪰ symbol; the intended relation is the upper bound forced by POVM normalization. A single consistent notation would avoid momentary confusion.","section":null},{"comment":"Lemma 3.2 and Lemma 4.6 invoke matrix Chernoff/Bernstein with a universal constant C or K; a one-line pointer to the precise form used (e.g., Tropp's matrix Chernoff) would make the numerical factors easier to track.","section":null},{"comment":"In the streaming reduction (proof of Theorem 1.2), the construction of q disjoint copies and dummy edges is clear, but a short remark that the algorithm's public randomness is shared and not charged to space would match the model stated in §2.1.","section":null},{"comment":"Typographical: 'Göös' appears with inconsistent diacritics in the abstract and introduction; 'eO' / 'eΩ' notation for polylog factors is introduced late and could be defined once at first use.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a clean, self-contained contribution that fits a theory journal well. The AI-assistance acknowledgment is unusually explicit; that is the authors' choice and does not affect the mathematical content. No novelty or citation concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper closes a real gap: the first tight Ω(N^{1/4}) one-way quantum communication lower bound for bipartite collision finding (improving Göös–Jain’s Ω(N^{1/12})), and the first nontrivial quantum streaming lower bound Ω(√Δ_V) for triangle finding that matches the classical √Δ_V term in the natural regime T=Θ(m), Δ_E=O(1), Δ_V≤m^{2/3}. Both are obtained by the same reusable technique rather than ad-hoc reductions.\n\nWhat is new is the measurement-discrepancy approach. Search problems produce whole POVMs, not a single acceptance operator. They absorb Bob-side validity into a PSD packing, center out the trivial baseline, and bound the remaining advantage by matrix Khintchine plus matrix Chernoff/Bernstein under the packing constraints forced by POVM normalization. The collision proof uses a random bipartition + bucket operators; the triangle proof uses the hard distribution with random bijections and a streaming-to-communication reduction. Both arguments are written out completely (Lemmas 3.1–3.2, 4.4–4.6, Theorems 1.1–1.2). The method also recovers the classical Kallaugher–Price √Δ_V lower bound without Boolean Hidden Matching, which is useful because BHM collapses quantumly.\n\nThe stress-test concern about packings that might evade the concentration bounds does not hold: every protocol induces a packing that satisfies exactly the hypotheses of those lemmas (P_ω ⪰ 0, ∑P_ω ⪯ I, and the pointwise bounds). Residual risk is ordinary human-proof error, not a conceptual hole. Soft spots are minor and already flagged by the authors: the triangle result is only for one-pass and a restricted parameter regime; multi-pass and the full classical parameterization remain open. Citations look solid and non-circular.\n\nThis is for people working on quantum communication complexity, streaming lower bounds, or matrix concentration methods. It deserves a serious referee. I would engage with it and expect it to be cited.","headline":"Tight one-way quantum lower bounds for two search problems via a clean matrix-discrepancy method that actually works.","tokens_in":23709,"tokens_out":527,"would_cite":true,"duration_ms":5211,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"A matrix-discrepancy method yields the first tight one-way quantum lower bounds for collision finding and streaming triangle finding.","keywords":["one-way quantum communication","search problems","matrix discrepancy","collision finding","triangle finding","quantum streaming","POVM packing","noncommutative Khintchine"],"falsifier":"Exhibit either a one-way quantum protocol for ColFind_{N,N+Ω(N)} that uses o(N^{1/4}) qubits and still succeeds with constant probability on uniform inputs, or a one-pass quantum streaming algorithm that finds a triangle on the hard family with o(√Δ_V) qubits of space.","tokens_in":23760,"feed_emoji":"⚛️","tokens_out":678,"duration_ms":6428,"temperature":0.7,"pith_summary":"Search problems allow many correct answers, so standard quantum lower-bound tools that reduce everything to a single yes/no bit lose power. This paper treats Bob’s entire family of measurement operators as one object and bounds their joint correlation with valid witnesses by a matrix-discrepancy quantity. The resulting technique produces an Ω(N^{1/4}) one-way quantum communication lower bound for bipartite collision finding, matching the classical birthday-paradox protocol, and an Ω(√Δ_V) one-pass quantum streaming lower bound for triangle finding on a natural hard family of graphs. In that regime the bound recovers the classical space lower bound without relying on a Boolean-Hidden-Matching reduction that fails for quantum protocols. The same packing-and-concentration argument therefore shows that quantum communication and streaming enjoy no asymptotic advantage for these two search tasks in the stated parameter ranges.","feed_headline":"Tight quantum lower bounds for collision and triangle search","feed_subtitle":"Matrix discrepancy shows quantum protocols need Ω(N^{1/4}) qubits and Ω(√Δ_V) stream space","key_machinery":"Matrix discrepancy of a centered PSD packing: after the Bob-side validity factors are absorbed into operators P_ω that sum to at most the identity, the protocol’s advantage is at most the expected operator norm of ∑(X_ω−EX_ω)P_ω, which is controlled by Khintchine plus a tailored concentration bound on the largest grouped block.","core_discovery":"One-way quantum protocols for search relations can be controlled directly by converting Bob’s POVM into a positive-semidefinite packing, subtracting the trivial guessing baseline, and bounding the remaining centered operator by a matrix-discrepancy estimate obtained from non-commutative Khintchine and matrix-concentration inequalities. Applied to collision finding this yields a tight Ω(N^{1/4}) qubit lower bound; applied to streaming triangle finding it yields an Ω(√Δ_V) space lower bound matching the best classical upper bound up to logs.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Matrix discrepancy gives tight quantum lower bounds for collision search","One-way quantum protocols need Ω(N^{1/4}) qubits for collision finding","Quantum streaming space for triangles hits Ω(√Δ_V) via matrix discrepancy","Joint POVM packing yields quantum lower bounds for search relations","Tight one-way quantum bounds for collision and triangle finding problems"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"Every successful protocol must induce a packing of positive-semidefinite operators whose grouped norms are forced by the problem’s combinatorial structure to obey the matrix-concentration bounds used in the discrepancy estimate.","fun_headline_variants_meta":{"raw":{"variants":["Matrix discrepancy gives tight quantum lower bounds for collision search","One-way quantum protocols need Ω(N^{1/4}) qubits for collision finding","Quantum streaming space for triangles hits Ω(√Δ_V) via matrix discrepancy","Joint POVM packing yields quantum lower bounds for search relations","Tight one-way quantum bounds for collision and triangle finding problems"]},"model":"grok-4.5","effort":"low","cost_usd":0.005136,"raw_usage":{"total_tokens":1498,"prompt_tokens":915,"num_sources_used":0,"completion_tokens":95,"cost_in_usd_ticks":51360000,"prompt_tokens_details":{"text_tokens":915,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":488,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":915,"tokens_out":95,"duration_ms":4522,"temperature":1.0,"reasoning_tokens":488,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T06:04:59.983344+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit either a one-way quantum protocol for ColFind_{N,N+Ω(N)} that uses o(N^{1/4}) qubits and still succeeds with constant probability on uniform inputs, or a one-pass quantum streaming algorithm that finds a triangle on the hard family with o(√Δ_V) qubits of space.","supporting_citations":[],"review_version":1}