{"id":"091faf04-f376-43e3-9219-853ff1dfa05f","arxiv_id":"2608.05775","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"For the inner product function, one-round f-routing requires shared state marginal dimension Ω(n/log n) even with two-sided diamond-norm error up to 0.09.","lead":"A new lower bound shows that one-round quantum f-routing of the inner product function needs a shared resource whose smaller marginal dimension grows at least as n/log n, even when the protocol is allowed a small error in both routing cases. The result is the first robust (two-sided error) logarithmic lower bound for this cost measure, improving on prior zero-error bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof hinges on Lemma 3's information-disturbance constant 2√ε; if the correct constant under the full diamond norm is 2√(2ε), the 0.09 gap closes and Theorem 1 fails.","rationale":"The reader correctly identified Lemma 3 as the weakest assumption, and I agree that this is the hinge of the proof. My read differs only in the recommended disposition: because the theorem's advertised error threshold 0.09 is tight against this exact constant, and because the paper explicitly treats Lemma 3 as an unproved hypothesis in the formalization, I would not accept unconditionally without an independent verification of the constant 2√ε under the full unhalved diamond norm. The rest of the argument is coherent and internally well-supported: Lemma 2's purification is valid, the SLD bounds in Lemma 5 are standard, the mixing step in Lemma 7 checks out algebraically, the rank bound in Lemma 12 is a genuine product-expansion/Fourier-sampling argument, and the sign-rank comparison is standard. No circularity or data fitting is apparent. The only place where a small constant change would destroy the theorem is the information-disturbance tradeoff, so a conditional acceptance pending that constant check is the appropriate verdict.","tokens_in":15196,"tokens_out":49527,"duration_ms":499652,"concrete_test":"Independently re-derive Lemma 3 from the continuity theorem in [KSW08] with the full, unhalved diamond norm, tracking the constant from isometry closeness to the reduced-channel diamond distance. Specifically, check whether the theorem yields ∥N_B − R_ζ∥⋄ ≤ 2√ε or 2√(2ε). Then recompute Equation (5): if the f=0 upper bound becomes 0.95·4√(2·0.09) ≈ 1.612 while the f=1 lower bound remains 0.95·2(0.91)² − 0.1 ≈ 1.473, the threshold θ=1.306695 no longer separates the cases and Theorem 1 as stated with ε=0.09 is false. If instead the constant 2√ε is confirmed, the existing gap of 0.333 in χ^s survives and the proof stands.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim rests on the exact constant in Lemma 3: a recovery error ε implies ∥N_B − R_ζ∥⋄ ≤ 2√ε. This enters Proposition 4 as the f(x,y)=0 bound ∥ρ^0−ρ^1∥_1 ≤ 4√ε, and via Lemma 5 and the mixing step with s=0.05 it produces the separating gap in Equation (5): χ^s ≤ 1.14 for f=0 versus χ^s ≥ 1.47339 for f=1. The whole sign-rank comparison in Section 5 needs this gap. If the continuity theorem in [KSW08] gives an isometry closeness of √(2ε) instead of √ε, then the corresponding diamond distance to the replacer is 2√(2ε), and the trace bound for f=0 becomes 4√(2ε) ≈ 1.697 for ε=0.09. The post-mixing upper bound would then be ≈ 1.612, while the f=1 lower bound is 1.47339, so no threshold θ can separate the two routing cases and the argument collapses. The paper itself flags Lemma 3 as a Lean hypothesis rather than a machine-checked theorem, and no commit hash is pinned, so the constant is not independently verified within the submission. This is not an internal inconsistency, but it is the single most load-bearing condition on the numerical threshold 0.09.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies one-round f-routing with a shared resource charged by E_dim(ρ_LR)=log_2 min{rank ρ_L, rank ρ_R}, with no limits on message lengths, local systems, or local operations. For f(x,y)=IP_n(x,y) (inner product mod 2), it claims that every protocol with worst-case error at most 0.09 in the full, unhalved diamond norm satisfies d log_2(2d)=Ω(n) for d=min{rank ρ_L, rank ρ_R}, and consequently E_dim(ρ_LR)≥log_2 n − log_2 log_2 n − O(1). The proof purifies the shared state to Schmidt rank d, applies an information-disturbance tradeoff to establish a constant trace-norm gap between the two routing cases, defines an SLD quadratic-form statistic χ(x,y) that inherits this gap, then shows (after mixing and Fourier/product-expansion arguments with explicit constant bookkeeping) that the matrix [χ^s(x,y)] is entrywise g/2-close to a real matrix of rank exp(O(d log(2d))) log(2N). Comparing this with the √N sign rank of the inner-product matrix yields the lower bound. A Lean 4 formalization machine-checks the internal proof, treating the information-disturbance tradeoff, the quantum-triangular-discrimination comparison, and the sign-rank bound as external hypotheses.","tokens_in":15403,"tokens_out":21736,"duration_ms":187256,"significance":"The result, if correct, is a meaningful advance: it gives the first growing lower bound on the charged shared-resource cost for an explicit routing function that allows two-sided error in both routing cases, in a model with unrestricted messages and local operations, and with arbitrary mixed shared states. The proof technique—converting routing correctness into an approximate-rank bound via an SLD quadratic form and then invoking a sign-rank lower bound—is novel and likely to be reusable. The paper is unusually explicit about its constants (s=0.05, θ=1.306695, g=0.166695), and the Lean 4 formalization of the internal argument is a valuable complement, even though the three external lemmas are not machine-checked. The main caveat is that the numerical threshold 0.09 depends on the exact constant in the external information-disturbance tradeoff, so the headline numerical claim carries a correctness risk that is not covered by the formalization.","major_comments":[{"comment":"The proof of Theorem 1 is critically sensitive to the exact constant 2√ε in Lemma 3. If the information-disturbance tradeoff from [KSW08, ABM+24] yields instead ∥N_B−R_ζ∥_⋄ ≤ 2√(2ε), then the f=0 bound in Proposition 4 becomes 4√(2ε) ≈ 1.70 at ε=0.09, and after the mixing step the upper value in Equation (5) becomes roughly 1.61, which exceeds the f=1 lower bound 1.47; the θ±g separation used in the sign-rank comparison of Section 5 would disappear. The manuscript does not prove Lemma 3 but cites [ABM+24] and asserts, without derivation, that the continuity theorem gives √ε isometry closeness. Please provide a complete derivation of Lemma 3, including the exact statement of the external theorem and the diamond-norm convention, or adjust the error parameter and the advertised 0.09 threshold to a value for which the separation holds.","section":"Section 3, Lemma 3 and Proposition 4; numerical gap in Equation (5)"},{"comment":"The paper explicitly states that the information-disturbance tradeoff, the comparison for measured quantum triangular discrimination, and the sign-rank bound are treated as hypotheses in the Lean formalization, and no commit hash is given. This makes the machine-checked claim conditional on the exact constants in these external results, in particular on the constant in Lemma 3 that drives the 0.09 threshold. The repository should record the precise statement of each axiom, with constants and norm conventions, and the paper should pin the repository version used. As it stands, the formalization cannot independently certify the robustness claim that is the paper's headline.","section":"Lean certification paragraph (after the Introduction) and Section 3, Lemma 3"}],"minor_comments":[{"comment":"Please cite the specific theorem numbers in [KSW08] and [ABM+24] that yield the √ε isometry closeness, and state which normalization of the diamond norm they use.","section":"Section 3, proof of Lemma 3"},{"comment":"The proof of the bound |F_ζ| ≤ M_j using noncommutative Hölder is only sketched; in particular, the case h_i=0 (where one uses the operator norm of a unitary) should be spelled out, since it is essential for the dimension independence.","section":"Section 4, proof of Lemma 12"},{"comment":"The term 'robust' is not formally defined; the introduction should state explicitly that it refers to allowing two-sided error in both routing cases.","section":"Title and Abstract"},{"comment":"The arXiv identifier or DOI for [ACM25] would help readers verify the comparison with the closest earlier result.","section":"Bibliography entry [ACM25]"}],"recommendation":"major_revision","confidential_remarks":"The paper is strong and the proof is mostly careful; the single most important issue is the unverified constant in Lemma 3, on which the advertised 0.09 depends. I recommend major revision rather than rejection because the issue is fixable either by a proof of the lemma or by adjusting the error threshold. I also note that the Lean formalization's conditional status should be made more precise. I saw no indication of circularity or misconduct."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The important thing to know about this paper: it delivers what it claims. It proves the first lower bound on the shared-resource cost E_dim for an explicit f-routing function that tolerates two-sided error, using the inner product modulo 2. The bound is only logarithmic, d = Ω(n/log n), but it improves on the zero-error Schmidt-rank bounds from ACM25, and the technique is genuinely new: converting correctness into a matrix with a constant gap, then controlling approximate rank via SLD quadratic form, mixing with a product state, Fourier expansions, and Chebyshev approximation.\n\nThe proof looks sound. I checked the constants that matter: the mixing step with s=0.05 leaves a gap around 0.167 between the two routing cases, and the approximation error g/2 preserves the sign pattern. The Lean 4 formalization machine-checks the internal argument; it treats the information-disturbance tradeoff, Liu's comparison, and Forster's sign-rank bound as hypotheses, which is honest and reasonable.\n\nThe stress-test concern about Lemma 3's constant does not survive reading the paper. Under the paper's explicit unhalved diamond norm, if ∥Φ - id∥⋄ = ε, then the normalized Choi states have trace distance ε; Uhlmann gives purifications with vector distance ≤ √ε, and reducing onto Bob's system loses a factor 2. So the correct bound is 2√ε, not 2√(2ε). The alternative constant would only appear under the halved norm. The gap does not close.\n\nThe soft spots are minor. The three external lemmas are load-bearing, and the paper doesn't reproduce KSW's theorem state—so a referee should verify that one constant, but it is right. The Lean artifact has no commit hash, so the formalization isn't pinned. And the lower bound remains logarithmic; the polynomial gap is still open, which the paper says plainly.\n\nWho is this for? People working on f-routing, non-local quantum computation, or quantum communication complexity more generally. It deserves a serious referee; the result is real, the proof is intricate, and the formalization is a plus.\n\nRecommendation: accept with the standard nudges—ask the author to pin the Lean version and state the exact lemma from KSW in the text. But don't send this back for major surgery; the center holds.","headline":"Genuine advance on f-routing lower bounds; the proof holds up and the stress-test worry about the information-disturbance constant is misplaced.","tokens_in":16012,"tokens_out":21998,"would_cite":true,"duration_ms":194100,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Even with 0.09 error allowed, one-round f-routing for inner product mod 2 forces shared states of rank Ω(n/log n).","keywords":["f-routing","non-local quantum computation","Schmidt rank","shared-resource cost","sign rank","information-disturbance tradeoff","quantum triangular discrimination","inner product mod 2"],"falsifier":"Exhibit an explicit one-round f-routing protocol for the inner product modulo 2 with worst-case diamond-norm error at most $0.09$ whose shared state has smaller marginal rank $d=o(n/\\log n)$; this would directly contradict Theorem 1. Alternatively, since the paper's machine-checked formalization treats the information-disturbance bound as a hypothesis, a concrete counterexample to Lemma 3 at $\\epsilon=0.09$ — an isometry and a recovery channel of error $0.09$ for which Bob's two reduced states differ in trace norm by more than $1.2$ — would close the constant gap and invalidate the proof.","tokens_in":14895,"feed_emoji":"⚛️","tokens_out":18125,"duration_ms":133497,"temperature":0.7,"pith_summary":"In one-round $f$-routing, Alice and Bob share a quantum state before receiving inputs; depending on the value of a public function $f$, either Alice or Bob must recover a qubit from their own final system. The paper proves that when $f$ is the inner product modulo 2, every protocol with worst-case error at most $0.09$ in both routing cases — even with unlimited message lengths and local operations — must pre-share a state whose smaller marginal support dimension $d$ is at least $c n/\\log n$ for an absolute constant $c$. The equivalent cost statement is $E_{\\dim}(\\rho_{LR})=\\log_2 d \\ge \\log_2 n - \\log_2\\log_2 n - O(1)$. The result matters because it is robust: the closest earlier growing lower bound for an explicit routing function required zero error in one routing case, while this one tolerates constant two-sided error. The proof works by converting correctness into a matrix with a constant gap between the two routing cases, approximating that matrix by a low-rank matrix whose rank depends only on $d$, and comparing with a sign-rank lower bound for the inner-product matrix.","feed_headline":"Qubit routing needs shared states of rank Ω(n/log n)","feed_subtitle":"Even 9% error in both recovery cases doesn't reduce the required shared-state dimension.","key_machinery":"The central object is the symmetric-logarithmic-derivative (SLD) quadratic form $\\chi_{SLD}(\\rho,\\sigma)=\\operatorname{Tr}[Z L_\\Sigma^+(Z)]$ with $\\Sigma=\\rho+\\sigma$, $Z=\\rho-\\sigma$, and $L_\\Sigma(X)=(\\Sigma X+X\\Sigma)/2$. This quantity — equal to twice the measured quantum triangular discrimination and to the Bures quantum $\\chi^2$ divergence — is the statistic that is both controlled by the trace-norm routing gap and compatible with the tensor-product expansions of Bob's states. The other load-bearing devices are the cost-preserving purification to a pure state of Schmidt rank $d$, the mixing of each state with a small product state $\\Omega_{x,y}=\\alpha_x\\otimes\\beta_y$ so the average state lies between two multiples of that product state, and the sign-rank lower bound for the Walsh–Hadamard matrix. The inverse of $L_{\\tau_{x,y}}$ is handled by a Fourier expansion whose complex powers separate into $x$-dependent and $y$-dependent factors precisely because $\\Omega_{x,y}$ is a product state; this separation is what makes the approximate rank depend only on $d$ and not on message dimensions.","core_discovery":"The central claim is Theorem 1: for the inner product modulo 2, $f_n(x,y)=\\bigoplus_{i=1}^n x_i y_i$, every protocol in the standard one-round $f$-routing model with worst-case error at most $0.09$ in the full, unhalved diamond norm satisfies $d\\log_2(2d)\\ge c n$ for an absolute constant $c>0$, where $d=\\min\\{\\operatorname{rank}\\rho_L,\\operatorname{rank}\\rho_R\\}$ is the smaller marginal support dimension of the pre-shared state. Consequently the cost $E_{\\dim}(\\rho_{LR})=\\log_2 d$ is at least $\\log_2 n-\\log_2\\log_2 n-O(1)$. The proof first shows that any mixed shared state can be replaced, at no extra cost, by a pure state of Schmidt rank $d$. It then uses the information-disturbance tradeoff to show that Bob's two states $\\rho^0_{x,y}$ and $\\rho^1_{x,y}$ differ in trace norm by at least $2(1-\\epsilon)$ when Bob must recover the qubit and by at most $4\\sqrt{\\epsilon}$ when Alice must; at $\\epsilon=0.09$ these bounds are $1.82$ and $1.2$, a constant gap. The symmetric-logarithmic-derivative statistic $\\chi(x,y)=\\chi_{SLD}(\\rho^0_{x,y},\\rho^1_{x,y})$ inherits this gap, and after mixing with a small product state and applying a Chebyshev-plus-Fourier approximation, the matrix $[\\chi(x,y)]$ is entrywise within $g/2$ of a real matrix of rank $\\exp(O(d\\log(2d)))\\log(2N)$, with $N=2^n$. Because the sign-rank of the inner-product matrix is at least $\\sqrt{N}$, comparing the two rank bounds forces $d\\log(2d)=\\Omega(n)$.","pith_inferences":["If the information-disturbance tradeoff constant were sharpened, the allowable error of $0.09$ could likely be increased and the same proof structure would survive; the paper does not explore this direction.","The final step's reliance on sign-rank suggests the result generalizes: any Boolean function with sign-rank $2^{\\Omega(n)}$ should admit the same $E_{\\dim}$ lower bound in this routing model, but the paper only proves this for inner product mod 2.","Because the paper's machine-checked formalization treats the information-disturbance tradeoff, the triangular-discrimination comparison, and the sign-rank bound as hypotheses, the theorem's correctness currently rests on those unverified external results; a rigorous attack would target them.","The cost measure charges shared randomness and separable correlations as well as entanglement, so the lower bound should be understood as a statement about all pre-shared correlations, not about entanglement specifically."],"forward_implications":["Any one-round $f$-routing protocol for the inner product modulo 2 with worst-case diamond error at most $0.09$ must pre-share a state whose smaller marginal rank is $\\Omega(n/\\log n)$, so communication and local operations cannot substitute for this shared resource.","The cost lower bound $E_{\\dim}(\\rho_{LR})\\ge \\log_2 n-\\log_2\\log_2 n-O(1)$ holds even though the proof never bounds message lengths, local systems, or local operations.","Because the rank bound depends only on $d$, the same style of argument applies to any function whose sign matrix has sufficiently large sign rank, with the inner product mod 2 being one such function.","A polynomial lower bound on $E_{\\dim}$ remains open; the paper's techniques yield only logarithmic growth, leaving a gap between $\\log n$ and any $n^\\delta$."],"supporting_citations":[{"why":"It supplies the continuity of Stinespring representations used in Lemma 3 to conclude that a nearly exact recovery by Alice leaves Bob's channel close to a replacer channel.","marker":"[KSW08]"},{"why":"It provides the diamond-norm information-disturbance statement for f-routing that yields the upper bound $4\\sqrt{\\epsilon}$ on the trace-norm difference between Bob's two states in the routing protocol.","marker":"[ABM+24]"},{"why":"It gives the inequalities $\\|\\rho-\\sigma\\|_1^2/2 \\le \\chi_{SLD}(\\rho,\\sigma) \\le \\|\\rho-\\sigma\\|_1$ for the measured quantum triangular discrimination, which convert the trace-norm routing gap into a gap for the SLD statistic.","marker":"[Liu25]"},{"why":"It yields the sign-rank lower bound $\\mathrm{signrank}(W_N)\\ge N/\\|W_N\\|_{\\mathrm{op}}=\\sqrt{N}$ for the inner-product sign matrix, used to finish the proof of Theorem 1.","marker":"[For02]"},{"why":"It supplies the variational representation of the inverse of a positive linear map used in Lemma 7 to bound the SLD statistic after mixing with the product state.","marker":"[BV04]"},{"why":"It provides the pinching inequality with the number-of-blocks constant used in Lemma 6 to upper-bound the average state by $d^2$ times a product state.","marker":"[OH04]"},{"why":"It gives the Chebyshev approximation construction for the reciprocal on a bounded interval used in Lemma 14 to express the statistic as a low-degree polynomial in the preconditioned operator.","marker":"[Saa03]"}],"fun_headline_variants":["Routing forces shared rank Ω(n/log n) even with 0.09 error","Logarithmic lower bound: routing eats shared dimensions","Proven: inner product routing needs Ω(n/log n) shared state","Shared-state cost for routing: Ω(n/log n) even with 9% error"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on a single borrowed bound: whenever one party can recover the qubit with error at most $\\epsilon$, the other party's two possible states must be within distance $4\\sqrt{\\epsilon}$ of each other; if that bound were any weaker, the constant gap between the two routing cases would disappear and nothing in the paper would go through.","fun_headline_variants_meta":{"raw":{"variants":["Routing forces shared rank Ω(n/log n) even with 0.09 error","Logarithmic lower bound: routing eats shared dimensions","Proven: inner product routing needs Ω(n/log n) shared state","Shared-state cost for routing: Ω(n/log n) even with 9% error"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000865,"raw_usage":{"total_tokens":3914,"prompt_tokens":1272,"completion_tokens":2642,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":888,"completion_tokens_details":{"reasoning_tokens":2562}},"tokens_in":888,"tokens_out":2642,"duration_ms":105540,"temperature":1.0,"reasoning_tokens":2562,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T23:42:55.715631+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit an explicit one-round f-routing protocol for the inner product modulo 2 with worst-case diamond-norm error at most $0.09$ whose shared state has smaller marginal rank $d=o(n/\\log n)$; this would directly contradict Theorem 1. Alternatively, since the paper's machine-checked formalization treats the information-disturbance bound as a hypothesis, a concrete counterexample to Lemma 3 at $\\epsilon=0.09$ — an isometry and a recovery channel of error $0.09$ for which Bob's two reduced states differ in trace norm by more than $1.2$ — would close the constant gap and invalidate the proof.","supporting_citations":[],"review_version":1}