Pith. sign in

REVIEW 2 major objections 6 minor 1 cited by

Quantum Separability in Polynomial Time

T0 review · 2 major / 6 minor · reviewed 2026-07-30 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For any fixed Euclidean gap, deciding whether a bipartite quantum state is separable can be done in randomized polynomial time.

desk verdict 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. read the letter →

arxiv 2607.23773 v1 pith:O63GJNPJ submitted 2026-07-26 quant-ph

Giulio Malavolta This is my paper · ORCID
classification quant-ph MSC 81P4068Q2590C22 PACS 03.67.Mn03.65.Ud
keywords quantumseparabilityweakmembershipFrobeniusnormseparablesupportfunctiondenseCSPHaarmeasuremean-fieldHamiltoniansBestState
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

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.

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 (2)
  1. [§3, Lemma 3.1 / Proposition 3.2 / Lemma 3.3] 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
  2. [§5.2, Theorem 5.7] 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.
minor comments (6)
  1. [§1.2 / Eq. (2)] 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.
  2. [§3, Lemma 3.1] ∥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.
  3. [§2.4] 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.
  4. [§5.3] 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').
  5. [Appendix A] 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.'
  6. [§1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: algorithmic reduction from h_Sep to dense CSP is by explicit construction, not self-definition or fitted prediction.

full rationale

This is a pure complexity/algorithms paper. The target quantities h_Sep(M) and Euclidean weak membership for Sep(d,d) are defined independently of the algorithm (Section 2.4, Eq. 1). The proof chain is a standard approximation-algorithm reduction: Hermitian decomposition (Eq. 2), Haar flattening (Lemma 3.3 from moment bounds 3.1–3.2), flat near-optimizers and dimension-free discretization (Lemmas 4.1–4.4), encoding of the penalized quartic Λ_D as a dense Max-4-CSP whose value equals Λ_D by direct expansion (Lemma 5.5), external dense-CSP PTAS (Theorem 5.2 / AKK95), and Frank–Wolfe membership (Section 5.3). Matching CSP value to the objective is intentional reduction design, not circularity: the optimum is not fitted to data, and no parameter is estimated from the quantity being predicted. Citations (hypercontractivity, Wick, AKK95, Frank–Wolfe) are external black boxes used as intended. No self-definitional loop, no fitted-input-called-prediction, no load-bearing self-citation uniqueness theorem, and no renaming of a known empirical pattern. Residual dependence on cited analytic tools is ordinary and does not raise the circularity score. Score 0; steps empty.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

The result is an algorithm resting on standard measure concentration, approximation algorithms, and convex optimization. No empirical fits. Load-bearing external theorems are the dense Max-k-CSP PTAS, Gaussian hypercontractivity/Wick, Haar sampling, and Frank–Wolfe convergence; the paper’s original analytic work is the flattening and discretization chain that feeds those black boxes.

assumptions (6)
  • standard math Dense Max-k-CSP admits a PTAS: for fixed k,|Ω|,δ, poly(n) time yields value within δ of OPT w.p. ≥2/3 (AKK95; YZ14 Thm 5).
    Invoked as Theorem 5.2; runtime poly(d) only because |Ω|=poly(1/η,log(1/δ)) is independent of d.
  • standard math Gaussian hypercontractivity for degree-m polynomial maps and Wick formula for complex Gaussians (Lemmas 2.2–2.3; ALM21).
    Used to prove Haar entry moment bounds in Lemma 3.1 and Proposition 3.2.
  • standard math Haar-random unitaries on U(d) can be sampled (exact or finite-precision coupled) in poly(d) arithmetic operations (Mez07; BGVKS23 for precision).
    Section 2.3 and Appendix A; algorithm applies U⊗V conjugation.
  • standard math Frank–Wolfe / conditional gradient on the convex set Sep yields weak membership from an approximate linear optimization oracle (Jag13-style analysis in §5.3).
    Section 5.3 potential f_ρ and step-size 2/(t+2); T=256/η^2 iterations.
  • domain assumption Separability and h_Sep are defined via convex hull of product pure states; Frobenius norm; partial-trace orthogonal decomposition (2)–(3).
    Standard quantum information setup in §§2.1 and 2.4; Euclidean gap is the promise.
  • domain assumption For fixed constant gap, small-d instances may be solved by existing quasi-poly methods (e.g. BCY11) so the new algorithm only needs d≥poly(1/τ).
    Explicit w.l.o.g. in proof of Theorem 5.7.
invented entities (2)
  • Flat/tail Hermitian decomposition after Haar conjugation (M_flat, M_tail)
    purpose: Isolate an entrywise small matrix on which dimension-free discretization applies, with Frobenius-small error.
    Constructive thresholding of entries of (U⊗V)*M(U⊗V); not a physical entity, but the central algorithmic object (Lemma 3.3).
  • Penalized quartic Λ_M and dense Max-4-CSP predicates P_a,b,c,e on alphabet E×E
    purpose: Turn continuous product-state optimization into a dense CSP whose OPT tracks h_Sep up to additive η+δ+O(d^{-1/2}).
    Defined in (11) and §5.2; encoding lemmas 5.3–5.6.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Separability in Polynomial Time." pith.science (2026). https://pith.science/paper/O63GJNPJ

@misc{pith2026260723773,
  author       = {Pith},
  title        = {Pith review of: Quantum Separability in Polynomial Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O63GJNPJ}},
  note         = {Machine review of arXiv:2607.23773}
}
abstract

The quantum separability problem asks whether a bipartite density matrix is separable or is $\eta$-far from every separable state. We give a randomized polynomial-time algorithm for this problem for every fixed constant gap $\eta>0$, when distance is measured in the Euclidean norm.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal Quantum de Finetti Theorems via Argmax Rounding

    quant-ph 2026-08 accept novelty 8.0 of 10

    Optimal quantum de Finetti error bounds are proven by sum-of-squares/argmax rounding, yielding subexponential separability algorithms and a counterexample to the exponential disentangler conjecture.

Reference graph

Works this paper leans on

20 extracted references · cited by 1 Pith paper

  1. [1]

    Physical Review Letters , year =

    Peres, Asher , title =. Physical Review Letters , year =

  2. [2]

    Separability of Mixed States: Necessary and Sufficient Conditions , journal =

    Horodecki, Micha. Separability of Mixed States: Necessary and Sufficient Conditions , journal =

  3. [3]

    Foundations of Computational Mathematics , year =

    Banks, Jess and Garza-Vargas, Jorge and Kulkarni, Archit and Srivastava, Nikhil , title =. Foundations of Computational Mathematics , year =

  4. [4]

    and Horodecki, Micha

    Donald, Matthew J. and Horodecki, Micha. The Uniqueness Theorem for Entanglement Measures , journal =

  5. [5]

    and DiVincenzo, David P

    Bennett, Charles H. and DiVincenzo, David P. and Smolin, John A. and Wootters, William K. , title =. Physical Review A , year =

  6. [6]

    and Rippin, M

    Vedral, Vlatko and Plenio, Martin B. and Rippin, M. A. and Knight, Peter L. , title =. Physical Review Letters , year =

  7. [7]

    Computable Measure of Entanglement , journal =

    Vidal, Guifr. Computable Measure of Entanglement , journal =

  8. [8]

    Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing , year =

    Gurvits, Leonid , title =. Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing , year =

Show all 20 references
  1. [9]

    Quantum Information and Computation , year =

    Gharibian, Sevag , title =. Quantum Information and Computation , year =

  2. [10]

    and Montanaro, Ashley , title =

    Harrow, Aram W. and Montanaro, Ashley , title =. Journal of the ACM , year =

  3. [11]

    and Parrilo, Pablo A

    Doherty, Andrew C. and Parrilo, Pablo A. and Spedalieri, Federico M. , title =. Physical Review A , year =

  4. [12]

    A Quasipolynomial-Time Algorithm for the Quantum Separability Problem , booktitle =

    Brand. A Quasipolynomial-Time Algorithm for the Quantum Separability Problem , booktitle =

  5. [13]

    Moments of Gaussian chaoses in Banach spaces , author=

  6. [14]

    2007 , journal =

    How to generate random matrices from the classical compact groups , author =. 2007 , journal =

    2007

  7. [15]

    International Symposium on Algorithms and Computation , year=

    Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur? , author=. International Symposium on Algorithms and Computation , year=

  8. [16]

    Journal of Physics A: Mathematical and General , year=

    Finite size mean-field models , author=. Journal of Physics A: Mathematical and General , year=

  9. [17]

    International Colloquium on Automata, Languages, and Programming , year =

    Shi, Yaoyun and Wu, Xiaodi , title =. International Colloquium on Automata, Languages, and Programming , year =

  10. [18]

    and Karpinski, Marek , title =

    Arora, Sanjeev and Karger, David R. and Karpinski, Marek , title =. Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing , year =

  11. [19]

    Proceedings of the 5th Innovations in Theoretical Computer Science Conference , year =

    Yoshida, Yuichi and Zhou, Yuan , title =. Proceedings of the 5th Innovations in Theoretical Computer Science Conference , year =

  12. [20]

    Proceedings of the 30th International Conference on Machine Learning , year =

    Jaggi, Martin , title =. Proceedings of the 30th International Conference on Machine Learning , year =

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.