{"id":"4e2926e5-a819-4df4-8671-a59362ec9cdb","arxiv_id":"2607.23773","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every fixed constant Euclidean gap η>0, bipartite quantum separability admits a randomized polynomial-time weak-membership algorithm.","lead":"A randomized algorithm decides, in time polynomial in dimension, whether a bipartite quantum state is separable or a fixed constant far from every separable state in Euclidean distance. This closes the long-open constant-gap Euclidean weak-membership question that previously had only quasi-polynomial algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"No internal gap found on tracing the proof chain; the load-bearing point is exactly the reader's: the q/d-per-factor scaling in Lemma 3.1 that powers Haar flattening. It is unverified but cheaply testable numerically.","rationale":"The reader identified the Haar-flattening lemma chain (3.1–3.3) as the weakest assumption, and my independent tracing confirms that is the right location: everything downstream (discretization, CSP encoding, Frank–Wolfe) is comparatively mechanical and checks out, while the moment bounds are the novel, self-contained, externally unverified core. I differ from the reader only in emphasis, not substance: (1) the reader worried about the high-probability flatness rate in Lemma 3.3, but the truncation/Markov bookkeeping there is standard; the genuinely crux quantity is the 1/d-per-Haar-factor scaling with linear q-growth in Lemma 3.1, since that exponent is what makes γ dimension-free — a failure there propagates silently because all later results treat γ parametrically. (2) The architecture is more robust than the reader's framing suggests: even a polylog degradation of the flatness bound would leave |Ω| = poly(1/η, log(1/δ)); only a lost power of d breaks the theorem. This robustness mildly lowers correctness risk but does not eliminate it, given the AI-assisted provenance and absence of any independent check. Credit where due: the argument is modular, the external tools (AKK95/YZ14 PTAS, ALM21 hypercontractivity, Jaggi Frank–Wolfe) are reputable and correctly instantiated, the decomposition and parameter bookkeeping in Theorem 5.7 close exactly at τ, and the finite-precision appendix addresses bit complexity plausibly. Because I found no internal inconsistency but the central analytic lemmas remain unverified for a breakthrough-scale claim, the reader's CONDITIONAL/MODERATE stands; my concrete test offers a cheap, proof-independent way to convert this into ACCEPT or REJECT.","tokens_in":21191,"tokens_out":11047,"duration_ms":424584,"concrete_test":"Numerically stress-test Proposition 3.2's scaling, bypassing the proof entirely. Take M = A⊗B with A,B fixed traceless Hermitian (so Tr₀M = Tr₁M = 0), normalized to ||M||_F = 1. For d ∈ {16, 32, 64, 128}, sample ~10⁴ independent Haar pairs (U,V) via QR of complex Gaussians, and for a fixed set of entry indices (a,b,c,e) estimate ||entry||_{L^{2p}} for p = 1..8. Fit the empirical decay in d: the paper predicts d^{-2}·p²·O(1). If the fitted exponent is ≈ −2, Lemma 3.3's flatness rate is confirmed and the dimension-free net stands; if it is ≈ −1 (or the p-growth is super-quadratic), γ = d²||D||_max grows with d, |Ω| is no longer dimension-free, and Theorem 5.7's polynomial runtime collapses. As a second independent check, directly measure max-entry of the rotated matrix and compare against c_flat(1+log(1/δ))²/d².","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the central claim (Theorem 5.7 → Corollary 5.9) as resting on one non-standard analytic input: Lemma 3.1's bound ||A(U H_ab U*)||_{L^q} ≤ c₁(q/d)||A||_F, applied twice in Proposition 3.2 to get entrywise L^{2p} norms of order p²/d², which via Lemma 3.3 yields ||M_flat||_max ≲ polylog(1/δ)/d². This 1/d² entry scaling is what makes γ = d²||D||_max dimension-free, hence what makes the ε-net alphabet |Ω| = poly(1/η, log(1/δ)) independent of d, hence what makes the dense-CSP PTAS polynomial in d. I traced the chain line by line — the Hölder split of ||G||^{-2} against the degree-2 polynomial factor (Lemma 2.1 inverse moment + Lemma 2.2 hypercontractivity), the Wick L² computation (Lemma 2.3), the polarization identity for a≠b, the double application of Lemma 3.1 in Prop. 3.2, the truncation tail bound in Lemma 3.3, the truncation/refill/renormalize argument in Lemma 4.1, the penalized rounding in Lemma 4.4/Claim 4.5, and the Frank–Wolfe recursion in §5.3 — and found each step internally consistent, including the constant bookkeeping (q vs 2q, c₀ vs c̃₀, the δ⁴ tail budget vs δ² failure probability). So I have no sharper objection than the reader's. But the concern is real, not manufactured: the entire breakthrough rests on roughly two pages of self-contained moment estimates, disclosed as AI-assisted, with no code, no formal verification, and no independent reproduction. The specific soft spot is the linear-in-q growth at 1/d per Haar factor: an off-by-two in the Hölder/hypercontractivity exponents, or a lost factor of d in the inverse-moment step, would degrade the entry bound from d^{-2} to d^{-1}, making γ grow like d·polylog and silently destroying dimension-freeness of the net — the architecture gives no downstream alarm if this happens, since all later lemmas take γ as a black-box parameter.","agreement_with_reader":"agree"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The manuscript gives, for every fixed constant gap η>0, a randomized poly(d)-time algorithm for weak membership in Sep(d,d) in Frobenius (Euclidean) distance, improving the quasipolynomial algorithm of Brandão–Christandl–Yard. The core is Theorem 5.7: an additive-τ approximation of the separable support function h_Sep(M) for Hermitian M with ∥M∥_F ≤ 1. The argument: (i) isolate the vanishing-partial-trace component C via the Hilbert–Schmidt orthogonal decomposition (Eq. (2)); (ii) conjugate by independent Haar unitaries and prove (Lemma 3.3, from the new moment bounds in Lemma 3.1 and Proposition 3.2) a flat+tail split with ∥C_tail∥_F ≤ δ and ∥C_flat∥_max ≲ polylog(1/δ)/d²; (iii) prove flat instances have flat near-optimizers and admit a dimension-free discretization over a constant-size net (§4); (iv) encode the penalized quartic as a dense Max-4-CSP on alphabet of size poly(1/τ) and apply the AKK/YZ PTAS (§5.2); (v) obtain weak membership via Frank–Wolfe (§5.3, Corollary 5.9). A bit-complexity upgrade is sketched in Appendix A.","tokens_in":21657,"tokens_out":10022,"duration_ms":305363,"significance":"If correct, this resolves a long-standing open problem: polynomial-time constant-gap Euclidean weak membership for separability, with consequences for the BSS problem in the ∥M∥_F ≤ 1 regime and polynomial-time mean-field ground-energy approximation. The result does not conflict with known barriers (Gurvits/Gharibian hardness is at small gap; Harrow–Montanaro at trace-norm scale). Strengths worth naming: the algorithm is fully constructive and falsifiable; the reduction is modular and uses only standard external black boxes (AKK95/YZ14 PTAS, Jaggi's Frank–Wolfe analysis); the novel analytic content (Haar flattening, dimension-free net) is self-contained and may be independently useful; there are no free parameters; and the finite-precision model is addressed. The principal verification burden is concentrated in roughly two pages of new moment estimates (§3), which are internally consistent on my reading but carry the entire claim.","major_comments":[{"comment":"The entire result rests on the entrywise moment bound ∥(u_a⊗u_c)*(U⊗V)*M(U⊗V)(u_b⊗u_e)∥_{L^{2p}} ≤ c₁p²/d²·∥M∥_F, powered by the q/d-per-Haar-factor rate in Lemma 3.1. I traced the derivation (Hölder split of ∥G∥^{-2} via Lemma 2.1 against the degree-2 factor via Lemma 2.2; the Wick L² computation via Lemma 2.3; polarization for a≠b; the double application in Prop. 3.2; the truncation in Lemma 3.3) and found each step internally consistent, including the constant bookkeeping. However, c₀, c₁, c_flat are purely existential and there is no independent corroboration of any kind. Given that these two pages carry the whole claim, I ask for: (a) explicit values or explicit upper bounds for c₀, c₁ and the resulting c_flat; (b) a short numerical sanity check of the p²/d² entrywise scaling at moderate d (this is cheap to implement and would materially raise confidence); (c) clarification of the i","section":"§3, Lemma 3.1 / Proposition 3.2 / Lemma 3.3"},{"comment":"The runtime is stated only as 'polynomial in d for fixed τ.' For a paper whose headline claim is polynomial time, the relevant quantities should be exhibited: the degree of the d-polynomial and the τ-dependence propagated through κ, λ, 1/ε = poly(γ, 1/η) (Lemma 4.4), γ = O(log²(1/δ)) (Lemma 5.3), the alphabet size |Ω| = poly(1/τ), and the exponent in the PTAS of Theorem 5.2. Please state the final runtime as an explicit function of d and τ, even if the τ-dependence is large; likewise for Corollary 5.9, where τ = η²/64 and T = 256/η² compound the dependence.","section":"§5.2, Theorem 5.7"}],"minor_comments":[{"comment":"The bound h_Sep(M) ≤ α + ∥A∥_F + ∥B∥_F + h_Sep(C) uses x*Ax ≤ ∥A∥_op ≤ ∥A∥_F; worth one phrase for the reader. Also, 'the term 2/√d becomes irrelevant' should point forward to the d ≥ 1024/τ² assumption in Theorem 5.7 and the small-d fallback.","section":"§1.2 / Eq. (2)"},{"comment":"∥A∥_F for a linear map A: L(C^d) → H is the Hilbert–Schmidt norm of the map (with L(C^d) carrying the Frobenius inner product); please define this explicitly, since it is later identified with ∥M∥_F via reshuffling in Proposition 3.2.","section":"§3, Lemma 3.1"},{"comment":"The asymmetric-dimension reduction Sep(d₀,d₁) → Sep(d,d) is a nice observation but interrupts the preliminaries; consider moving it to an appendix or to §5.3 where weak membership is treated.","section":"§2.4"},{"comment":"Typo in step (ii): 'runℓindependent instances the algorithm' — missing 'of'. There are also several missing spaces around inline math in the arXiv build (e.g., 'isη-far', 'ind').","section":"§5.3"},{"comment":"The claim that ∥Ũ−U∥_op ≤ r/100 on each factor yields ∥C̃ − Ĉ∥_F ≤ r involves expanding four conjugation factors; please show the constant accounting. Similarly, justify the assertion that after increasing the cutoff by r, 'every entry in the new tail belongs to the original tail.'","section":"Appendix A"},{"comment":"A short paragraph delineating this result from hardness in neighboring regimes (trace-norm scale in [HM13]; hypercontractive/2→4-norm hardness for tensor optimization, e.g., Barak et al.) would help readers see why the ∥M∥_F ≤ 1, constant-additive-error regime is not covered by known barriers.","section":"§1"}],"recommendation":"minor_revision","confidential_remarks":"This claims to resolve a prominent open problem, and the author discloses that ChatGPT assisted with the proofs of all technical statements in the reduction. My own line-by-line reading of §3–§5 found the steps internally consistent — I could not identify a gap, and the crucial q/d-per-factor scaling in Lemma 3.1 is derived, not assumed. Nevertheless, given the stakes and the provenance, I would advise a second referee with random-matrix/moment-method expertise to independently verify Lemma 3.1 through Lemma 3.3 before final acceptance, and I support asking the authors for explicit constants and a small numerical corroboration script. No concerns about citation pattern or fit with the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The punchline is simple: Malavolta claims a randomized poly(d) algorithm for constant-gap Euclidean weak membership in Sep(d,d), plus the matching support-function approximation. That was the open constant-accuracy Euclidean question left after Gurvits/Gharibian hardness and the Brandão–Christandl–Yard quasipolynomial hierarchy. If true, it moves the algorithmic baseline.\n\nWhat is actually new is the reduction path, not the black boxes. Orthogonal split to a vanishing-partial-trace C, independent Haar conjugation, high-probability flat+tail split with max-norm O(polylog(1/δ)/d²), proof that flat instances have bounded-amplitude near-optimizers, dimension-free ε-net (alphabet size independent of d), dense Max-4-CSP via the AKK/YZ PTAS, then Frank–Wolfe for membership. The external tools are standard and cited correctly. The novel analytic work is the entrywise L^{2p} bound after Haar (Lemma 3.1 → Prop 3.2 → Lemma 3.3) that makes γ = d²||D||_max dimension-free; everything downstream is then polynomial for fixed η.\n\nI traced the chain the same way the stress-test did. Hölder + inverse Gaussian moment + hypercontractivity + Wick + polarization look internally consistent, including the constant bookkeeping. No obvious off-by-d that would silently kill dimension-freeness. Soft spots are real but proportionate: the load-bearing moment estimates are self-contained, AI-assisted by the author’s own disclosure, and have no code or formal check. An error of a factor of d in the 1/d-per-factor scaling would break the result without a later alarm. Appendix A on finite precision is a sketch, not a full bit-complexity proof. Citation pattern is appropriate; no circularity.\n\nThis is for people who care about algorithmic entanglement, mean-field ground energies, and BSS in Frobenius norm. It deserves a serious referee who will re-derive Lemmas 3.1–3.3 and 4.1–4.4, not a desk reject. I would bring it to reading group and engage; if the moments hold, I would cite it. Send it out.","headline":"If the Haar-flattening lemmas check out, this is the poly-time constant-gap Euclidean separability algorithm people have wanted since BCY11; the architecture is clean and the soft spot is concentrated in a few pages of moment bounds.","tokens_in":21781,"tokens_out":587,"would_cite":true,"duration_ms":20138,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P40","68Q25","90C22"],"pacs":["03.67.Mn","03.65.Ud"],"model":"grok-4.5","headline":"For any fixed Euclidean gap, deciding whether a bipartite quantum state is separable can be done in randomized polynomial time.","keywords":["quantum separability","weak membership","Frobenius norm","separable support function","dense CSP","Haar measure","mean-field Hamiltonians","Best Separable State"],"falsifier":"Implement the claimed support-function algorithm on a family of explicit vanishing-partial-trace Hermitians whose true h_Sep is known independently; if the returned product vectors systematically fall short of the optimum by more than the promised constant, or if the flat-tail split fails at the stated probability, the central claim is false.","tokens_in":21336,"feed_emoji":"⚛️","tokens_out":958,"duration_ms":17308,"temperature":0.7,"pith_summary":"Deciding whether a bipartite quantum density matrix is separable—or at least a fixed distance away from every separable state—has long been known to be hard when the allowed error shrinks with dimension. This paper shows that once the gap is any fixed positive constant and distance is measured in the Euclidean (Frobenius) norm, a randomized algorithm finishes in time polynomial in the local dimension. The route is to approximate the separable support function of a bounded Hermitian matrix, then turn that optimizer into a weak-membership tester by Frank–Wolfe iteration. A sympathetic reader cares because constant-gap Euclidean separability is a basic computational primitive in quantum information; a genuine polynomial-time algorithm upgrades several quasi-polynomial results and supplies an efficient handle on best-separable-state and mean-field ground-energy questions under the same norm.","feed_headline":"Quantum separability decided in polynomial time","feed_subtitle":"Any fixed Euclidean gap is enough; the algorithm runs in time poly in the local dimension.","key_machinery":"Haar-random local basis change followed by a flat-plus-tail decomposition: after conjugating a vanishing-partial-trace Hermitian by independent Haar unitaries, the matrix splits (with high probability) into an entrywise-flat piece whose product-state optimum can be discretized onto a dimension-free alphabet and solved by a dense Max-4-CSP PTAS, plus a small-Frobenius tail that perturbs the optimum by only a controllable additive error.","core_discovery":"For every fixed constant gap η>0 there is a randomized algorithm running in time polynomial in d that, given a bipartite density matrix on C^d⊗C^d, accepts every separable state and rejects every state that is more than η away from Sep(d,d) in Frobenius distance. Equivalently, the separable support function of any Hermitian M with Frobenius norm at most 1 can be approximated to any fixed additive accuracy in randomized polynomial time.","pith_inferences":["The same flatness-plus-dense-CSP pattern may apply to other constant-gap tensor optimization problems whose objectives become entrywise small after random local rotations.","Because the algorithm is tied to the Frobenius norm, an analogous polynomial-time result for constant-gap trace-norm or LOCC-norm separability remains open and would need a different flattening argument.","Finite-precision Haar sampling is already sketched; a fully derandomized version would remove the last source of randomness if an explicit unitary ensemble with matching moment bounds exists."],"forward_implications":["Weak membership for Sep(d,d) with any fixed Euclidean gap η>0 is in randomized polynomial time.","The Best Separable State problem admits a polynomial-time additive approximation whenever the objective has Frobenius norm at most 1.","Ground-state energies of mean-field Hamiltonians with product-pair interactions can be approximated to error proportional to the Frobenius norm of the interaction in polynomial time.","The earlier quasi-polynomial guarantees for constant-accuracy Euclidean separability are improved to genuine polynomial time."],"fun_headline_variants":["Fixed-gap quantum separability falls in randomized poly-time","Euclidean gap η>0 puts bipartite separability in randomized P","Separable states vs η-far: poly-time randomized test for any fixed η","Frobenius-gap separability decided in time poly in local dimension","Approx separable support function to fixed accuracy in randomized P"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"After a random local change of basis, matrices with vanishing partial traces really do become entrywise almost flat except for a small-Frobenius tail, at the quantitative rate needed for the net size to stay independent of dimension.","fun_headline_variants_meta":{"raw":{"variants":["Fixed-gap quantum separability falls in randomized poly-time","Euclidean gap η>0 puts bipartite separability in randomized P","Separable states vs η-far: poly-time randomized test for any fixed η","Frobenius-gap separability decided in time poly in local dimension","Approx separable support function to fixed accuracy in randomized P"]},"model":"grok-4.5","effort":"low","cost_usd":0.00381,"raw_usage":{"total_tokens":1060,"prompt_tokens":583,"num_sources_used":0,"completion_tokens":94,"cost_in_usd_ticks":38104000,"prompt_tokens_details":{"text_tokens":583,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":383,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":583,"tokens_out":94,"duration_ms":61787,"temperature":1.0,"reasoning_tokens":383,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T12:59:46.499962+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Implement the claimed support-function algorithm on a family of explicit vanishing-partial-trace Hermitians whose true h_Sep is known independently; if the returned product vectors systematically fall short of the optimum by more than the promised constant, or if the flat-tail split fails at the stated probability, the central claim is false.","supporting_citations":[],"review_version":1}