Pith. sign in

REVIEW 4 major objections 5 minor 3 references

A Simple Algorithm for Best Separable State

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read For measurements that accept some product state with probability 1, a pinning-based rounding finds near-optimal product states in time $n^{O(\sqrt{n/\varepsilon})}$ and product states with value $q/n$ in time $n^{O(\sqrt{q})}$.

desk verdict The 1 vs 1–ε result is a real, likely-correct advance; the 1 vs q/n result rests on a false lemma and is currently unsupported. read the letter →

arxiv 2608.10147 v1 pith:PHQZ7GEL submitted 2026-08-10 cs.DS quant-ph

Prashanti Anderson , Samuel B. Hopkins , Amit Rajaraman This is my paper · ORCID
classification cs.DSquant-ph MSC 68Q1768W2081P6890C22
keywords bestseparablestatesum-of-squaresrelaxationglobalcorrelationroundingpinninglemmaquantumMerlin-Arthurgamesrank-onematrixapproximationpolynomialoptimizationconditioning
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

The paper studies the best separable state problem: given a Hermitian matrix $M$ with $0 \preceq M \preceq I$, find the maximum of $\langle x \otimes y, M(x \otimes y)\rangle$ over unit vectors $x,y$, i.e. the largest acceptance probability of a measurement over unentangled states. In the perfect completeness case, where some product state is accepted with probability $1$, the paper claims a simple rounding algorithm for the sum-of-squares relaxation that finds a product state with value at least $1-\varepsilon$ in time $n^{O(\sqrt{n/\varepsilon})}$, and a product state with value at least $q/n$ in time $n^{O(\sqrt{q})}$. These running times improve the previous best exponents, and the search versions are solved in the same time. The argument is carried by iterated coordinate conditioning, with a potential function on conditional means, plus a new fine-grained pinning lemma stated as a measure decomposition of independent interest.

What carries the argument

The load-bearing mechanism is a pinning lemma built on global correlation rounding. Starting from a degree-$t$ SoS pseudo-distribution over a discretized sphere, the algorithm conditions on coordinate values one at a time; the potential $\Phi(u,v)=2(\|u\|^2+\|v\|^2+\|u\|\|v\|)$ on the conditional means increases by a fixed multiplicative factor whenever the desired small-covariance or low-soundness condition fails, so the number of conditioning steps is bounded by the budget $O(\sqrt{n/\varepsilon})$ or $O(\sqrt{q})$. The success condition for the $1-\varepsilon$ regime is $\|\mathrm{Cov}(x,y)\|_F \le \gamma \|\mathbb{E}x\|\,\|\mathbb{E}y\|$; when it holds, the mean pair is close to the accepting subspace because the relaxation forces $\mathbb{E}[x\otimes y]$ to lie in it. For the $q/n$ regime, affine-square reweighting is added and the final output is chosen among two best-response candidates and the top singular vectors of $R=\mathbb{E}[xy^\top]$.

What would settle it

For $q=2$ and large $K$, check whether Lemma 5.4's bounds can hold: with $\theta=K\sqrt{2/n}$, the asserted lower bounds $\|\mathbb{E}'x\|, \|\mathbb{E}'y\| \ge c\theta\sqrt{n}$ individually exceed $1$ for unit vectors, so a direct counterexample to the lemma exists if the claim is taken literally; constructing one would settle whether the $n^{O(\sqrt{q})}$ theorem is correct.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1.2, is that under $\mathrm{BSS}(M)=1$ the SoS relaxation can be rounded by pinning only $O(\sqrt{n/\varepsilon})$ coordinates (for the $1-\varepsilon$ guarantee) or $O(\sqrt{q})$ coordinates and affine-square reweightings (for the $q/n$ guarantee). After that many steps, either the conditional cross-covariance is small compared with the product of the conditional means, or one of three low-soundness win conditions holds; the corresponding mean pair, best response, or top singular-vector pair then has the claimed value. The analysis shows the relaxation is infeasible in the NO cases, and in the YES case every witness can be discretized to a feasible point. The paper separately proves a fine-grained pinning lemma: a distribution on the sphere can be decomposed by conditioning on $O(\sqrt{n}/\gamma)$ coordinates, sampled so the decomposition is exact, and the expected Frobenius norm of the conditional covariance is at most $O(\gamma)$ times the expected squared drift of the conditional mean.

Load-bearing premise

The $q/n$ part of the main theorem depends on Lemma 5.4, which asserts that after $O(\sqrt{q})$ pinning/reweighting operations one of three win conditions always holds together with specific quantitative lower bounds; if that lemma fails, the $n^{O(\sqrt{q})}$ guarantee is not established.

Editorial extensions

If this is right

  • For $\mathrm{BSS}(M)=1$ versus $\mathrm{BSS}(M)\le 1-\varepsilon$, the $n^{O(\sqrt{n/\varepsilon})}$ runtime is subexponential for every $\varepsilon = n^{-1+\Omega(1)}$, which was not achieved by the previous $\exp(\sqrt{n}(\log n)^{O(1)}/\varepsilon^2)$ algorithm.
  • For $\mathrm{BSS}(M)=1$ versus $\mathrm{BSS}(M)\le q/n$, the $n^{O(\sqrt{q})}$ runtime improves on the earlier $n^{O(q)}$ algorithm whenever $q\gg \log^2 n$.
  • Both algorithms solve the search versions in the same running time, producing explicit unit vectors $x,y$ with the claimed acceptance probability.
  • The fine-grained pinning lemma gives an exact measure decomposition of a spherical distribution into conditionals with controlled covariance-to-mean-drift ratio, using $O(\sqrt{n}/\gamma)$ coordinates, and it applies to pseudo-distributions of corresponding degree.
  • Since BSS generalizes finding the closest rank-one matrix to a subspace guaranteed to contain one and upper-bounds two-prover quantum Merlin-Arthur games, the new exponents carry over as algorithmic upper bounds in those settings.

Reading between the lines

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

  • The paper does not explore whether the exhaustive enumeration over all conditioning branches can be replaced by randomized or adaptive branch selection; if it can, the same pinning analysis would likely give a Las Vegas-style rounding with the same guarantees.
  • The potential-growth argument is not obviously specific to product states: any degree-4 relaxation whose pseudo-moment is constrained to lie in a subspace may admit the same low-soundness reweighting template, so the $n^{O(\sqrt{q})}$ tradeoff may transfer to other rank-one-in-subspace problems.
  • The tightness example for the fine-grained pinning lemma suggests the $\sqrt{n}$ in the exponent may be inherent for pinning-based rounding; reducing it to $O(\log n)$ would require a different primitive, not just a sharper potential analysis.
  • One testable extension is to benchmark the conditioning budget empirically on planted instances: if the number of pinnings actually needed scales like $\sqrt{n/\varepsilon}$ rather than $\log n$, that would support the analysis being tight rather than loose.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper studies the Best Separable State (BSS) problem in the perfect-completeness regime, where a measurement operator M with BSS(M)=1 is given and the goal is to find product vectors x,y achieving value close to 1, or at least q/n for a parameter q. The main claimed contribution, Theorem 1.2, is an algorithm with running time n^{O(sqrt(n/epsilon))} for the 1 versus 1-epsilon regime and n^{O(sqrt(q))} for the 1 versus q/n regime, improving on the prior works [BKS17] and [BGGLT17]. The algorithm is a global-correlation-rounding scheme for the sum-of-squares relaxation, with a new potential-function analysis, and the paper also states a fine-grained pinning lemma of independent interest. The 1 versus 1-epsilon section develops a pinning lemma and a mean-rounding success condition; the 1 versus q/n section introduces affine reweighting, multiple final rounding steps, and a Lemma 5.4 that is supposed to guarantee certain lower bounds on the conditional means and on the Frobenius norm of the second-moment matrix. The fine-grained pinning lemma in Section 6 is proved via a potential-function recurrence.

Significance. If the claimed guarantees were correct, the paper would represent a substantial algorithmic improvement over the state of the art for BSS, and the fine-grained pinning lemma would be a useful measure-decomposition tool. The high-level approach of combining global correlation rounding with carefully chosen potential functions is appealing, and the warmup presentation in Section 2 is pedagogically valuable. The paper also gives credit to prior work and includes an unusually detailed AI-usage disclosure. However, the main second guarantee rests on a lemma that is internally inconsistent, and the first guarantee's pinning lemma also contains a scale error in its statement. These issues are not merely presentation problems: the proof of Theorem 5.1 and hence the advertised n^{O(sqrt(q))} bound are unsupported as written. The fine-grained pinning lemma in Section 6 appears plausible and is presented with a coherent recurrence analysis, but it cannot rescue the BSS claims.

major comments (4)
  1. [Section 5.2, proof of Lemma 5.4] Lemma 5.4 cannot hold as stated. For any pseudodistribution satisfying (9), the universal bounds ||E'x|| <= (1+n^{-beta})^{1/2}, ||E'y|| <= (1+n^{-beta})^{1/2}, and ||E'xy^T||_F <= (E'||x||^2)^{1/2}(E'||y||^2)^{1/2} <= 1+n^{-beta} follow from Jensen/Cauchy-Schwarz for pseudo-expectations. In the application in Theorem 5.1, theta = K sqrt(q/n), so theta sqrt(n) = K sqrt(q). Taking q=2 and n large enough that theta < c, part (b) of Lemma 5.4 asserts ||E'xy^T||_F is at least a constant times K sqrt(2), which exceeds the universal upper bound whenever the constant is positive and K is chosen large. Part (a) similarly asserts cK sqrt(q) >= 1 for K >= 1/(c sqrt(q)). The proof's instruction to choose K 'sufficiently large' therefore makes the contradiction unavoidable.
  2. [Section 5.6, proof of Theorem 5.1] The balancing in the proof of Lemma 5.4 is dimensionally inconsistent. The first phase costs O(Qn) pinnings by Lemma 4.7, and the second phase is bounded by O(theta^2/Q) increments. The sum Qn + theta^2/Q is minimized at Q = theta/sqrt(n), not at Q ~ theta sqrt(n) as claimed. With the claimed choice Q ~ theta sqrt(n), the total operation count becomes O(theta n^{3/2}), not O(theta sqrt(n)). With the correct balancing Q = theta/sqrt(n), the mean-anchoring step only yields ||m_x||, ||m_y|| >= theta^{1/2} n^{-1/4}, not the c theta sqrt(n) lower bounds asserted in parts (a) and (b). Thus neither the operation count nor the auxiliary bounds of Lemma 5.4 follow from the proof as written.
  3. [Section 4.2, Lemma 4.5(b)] The final rounding argument for the 1 versus q/n regime depends essentially on the false auxiliary bounds in Lemma 5.4. In the singular-value case, the proof needs ||R||_F >= sqrt(q)/n to control the additive n^{-2} error in Lemma 5.3; Lemma 5.4(b) would supply this only if it were true, and it is not. In the mean case, the proof uses Lemma 5.4(a) to ensure that the best-response candidates exceed q/n. Since Lemma 5.4 is false, Theorem 5.1 and hence the second guarantee of Theorem 1.2 are unsupported. The reader's secondary point that sqrt(q)/n is not a consequence of Lemma 5.4 is not the core issue: if part (b) held at the stated theta sqrt(n) scale, the implication would be immediate. The core issue is that part (b) is impossible under the unit-norm constraints.
  4. [Section 4.4, proof of Theorem 4.1] The same type of scale error appears in the 1 versus 1-epsilon section. Lemma 4.5(b) asserts that the conditioned means satisfy ||E'x||, ||E'y|| >= gamma sqrt(n) for every 0 < gamma <= 1. For gamma sqrt(n) > 1, which occurs for any fixed positive epsilon when n is large, this violates the universal upper bound ||E'x|| <= (1+n^{-beta})^{1/2}. The proof of Theorem 4.1 uses part (b) only to control the term n^{-beta}/(||m|| ||q||), and a much weaker lower bound of order gamma/sqrt(n), or the gamma^{-1/2} n^{-1/4} actually delivered by the mean-anchoring step with Q ~ 1/(gamma sqrt(n)), would suffice for that purpose. This is a local fix, unlike the Section 5 issue, but as stated Lemma 4.5 is false and the proof of Theorem 4.1 cites the false statement.
minor comments (5)
  1. [Algorithm 4.3] The exposition of the first phase mixes squared and unsquared norm notation: 'both ||E x||_2 and ||E y||_2 will be at least sqrt(log n/(epsilon n))' should refer to the square of the norm or to the contribution to the squared norm, and the subsequent display 'epsilon * ||E x||_2^2 ||E y||_2^2 >= 1/2 * sqrt(epsilon log n/n) * Phi' should be written with consistent quantities.
  2. [Section 6, Lemma 6.1] The notation in Algorithm 4.3 is confusing: the variable eE is reused for both the input pseudodistribution and the conditioned pseudodistribution, and the symbol eEr appears without definition. Please introduce distinct names for the input, the conditioned object, and the pseudo-expectation operator.
  3. [Section 5.4] The relationship between the parameter gamma in Lemma 6.1 and the parameter epsilon in the stated Theorem 2.7 is not made explicit. A reader cannot directly verify that the two statements are equivalent, especially because Theorem 2.7 is phrased as an upper bound on E||Cov||_F in terms of the mean, while Lemma 6.1 is phrased as a lower bound on the mean drift in terms of E||Cov||_F. Please state the parameter translation and show that the displayed min{} expression is the correct formal version of the informal statement.
  4. [Section 2.4, Figure 1] In the proof of Lemma 5.14, the line 'E[XY] = sigma_x^2(-1/2 + O(delta) + O(sqrt(delta Q)/sigma_x))' should specify whether the final error term is negligible compared to the main term under the stated assumptions. The current presentation makes the subsequent substitution 'sqrt(Q)/sigma_x <= ||m_x||/sigma_x' appear only after the fact.
  5. [Section 1, AI usage statement] The caption of Figure 1 says 'noticeable fraction of conditional distributions' but the theorem statement is an in-expectation statement over the measure decomposition. Please clarify whether the intended claim is an expectation bound or a positive-measure bound.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main results are proven against independent prior algorithms with no fitted inputs recycled as predictions.

full rationale

The paper's central claims are algorithm existence theorems with explicit proofs, and no target quantity is fitted from data and then renamed as a prediction. The BSS rounding guarantees in Theorem 1.2 are established through potential-function arguments over pseudodistributions, with comparisons to the independent algorithms of Barak-Kothari-Steurer [BKS17] and Bhattiprolu-Ghosh-Guruswami-Lee-Tulsiani [BGGLT17]. The self-citations in the paper are confined to related-work context ([ABH26] for global correlation rounding in low-rank approximation) and to standard sum-of-squares background exposition ([ABMT25] in Section 3). Neither self-citation is load-bearing for the new results: the SoS preliminaries are standard material also traced to Barak-Steurer's lecture notes, and the proof of the main theorems does not invoke [ABH26] or [ABMT25] as a source of the pinning or rounding claims. The suspected internal inconsistency in Lemma 5.4 identified by the critical reader is a mathematical correctness concern, not a circularity one: it concerns whether the stated lower bounds are entailed by the pseudodistribution constraints, not whether an output is equivalent to an input by construction. Therefore the derivation chain is self-contained with respect to circularity, and the appropriate score is 0.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim relies on standard SoS machinery, the reduction to real projectors, and a prior variance-drop inequality. The free parameters are algorithm design choices, not data-fitted values. No new physical or mathematical entities are postulated.

free parameters (3)
  • epsilon, gamma, T = gamma = sqrt(epsilon)/4, T = ceil(C sqrt(n)/gamma)
    Tuning constants in Algorithm 4.2. They are not fitted to data, but the running-time exponent n^{O(sqrt(n/epsilon))} depends on this choice.
  • Q = Q = 1/(gamma sqrt(n)) in Lemma 4.5; stated as Q = theta sqrt(n) in Lemma 5.4
    Balance parameter between first-phase pinning and second-phase potential growth. The Section 5 value as printed is dimensionally inconsistent.
  • theta, K, beta = theta = K sqrt(q/n), beta = 2 or 4
    Proof constants in Sections 4 and 5 and the slack parameter in the relaxed constraints A'(beta). They are chosen to make the rounding bounds exceed the required soundness threshold.
assumptions (4)
  • standard math Sum-of-squares optimization, weak separation, and conditioning facts (Fact 3.4, Theorem 3.5, Definition 3.6) from [Sho87, Nes00, Par00, Gri01, GLS81].
    This is the standard machinery that lets the algorithm solve and manipulate pseudo-distributions in n^{O(t)} time.
  • standard math Variance-drop inequality from [BRS11] (Fact 6.3), used to lower-bound potential growth.
    Invoked in the potential-function arguments in Sections 2, 4, 5, and 6. It is a standard prior lemma.
  • domain assumption Reduction of complex BSS to the real-valued projector case in the perfect-completeness setting, following [BKS17, Section B].
    The proofs work over R and assume M is a projector. This reduction is cited, not reproved.
  • domain assumption Discretization of the unit sphere to a finite grid with slack A'(beta) is harmless.
    The grid approximation introduces 1/poly(n) errors that the proofs claim are absorbed by the beta = 2 or beta = 4 slack constraints.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Simple Algorithm for Best Separable State." pith.science (2026). https://pith.science/paper/PHQZ7GEL

@misc{pith2026260810147,
  author       = {Pith},
  title        = {Pith review of: A Simple Algorithm for Best Separable State},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PHQZ7GEL}},
  note         = {Machine review of arXiv:2608.10147}
}
abstract

We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms, the goal is to maximize $\langle(x \otimes y), M (x \otimes y)\rangle$ over unit vectors $x,y$ where $0 \preceq M \preceq I$; we call this value $\mathrm{BSS}(M)$. We study $\mathrm{BSS}$ in the "perfect completeness" regime, where given $M$ such that $\mathrm{BSS}(M) = 1$ the goal is to find the best possible solution $x,y$ -- this generalizes the problem of finding a rank-one matrix as close as possible to a given subspace of $\mathbb{R}^{n \times n}$ guaranteed to contain a rank-one matrix. The strongest known algorithmic guarantees for this problem are: (1) an algorithm which finds a solution with value $1-\varepsilon$ in time $\exp(\sqrt{n} (\log n)^{O(1)} / \varepsilon^2)$, due to Barak, Kothari, and Steurer, and (2) an algorithm which finds a solution with value $q/n$ in time roughly $n^{O(q)}$, due to Bhattiprolu, Ghosh, Guruswami, Lee, and Tulsiani. We give a much simpler approach to rounding the SoS relaxation, generalizing the canonical "global correlation rounding" technique, and obtain a better running time. Given $M$ with $\mathrm{BSS}(M) = 1$, our algorithm finds a solution with value $1-\epsilon$ in time $n^{O(\sqrt{n/\varepsilon})}$, and a solution of value $q/n$ in time $n^{O(\sqrt q)}$. Using the same techniques, we prove a new variant of the "pinning lemma", a measure-decomposition theorem widely used in LP/SDP rounding, high-dimensional probability, and statistical physics, which we believe is of independent interest.

Figures

Figures reproduced from arXiv: 2608.10147 by the authors.

Figure 1
Figure 1. Two ways that ∥ Cov ∥F can decrease as we condition on coordinates in a high￾dimensional distribution. In the top row, correlations disappear while the conditional mean remains near the origin – the distribution becomes isotropic but retains significant variance. In the bottom row, the overall variance decreases while the mean moves away from the origin. Our fine-grained pinning lemma shows that the second behavior … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

  1. [403]

    Estimating Random Variables from Random Sparse Observations

    DOI: 10.1002/ett.1289. arXiv: 0709.0145 [cs.IT] (pages 2, 9). [Nes00] Yurii Nesterov. “Squared functional systems and optimization problems”. In: High performance optimization. Springer, 2000, pp. 405–440 (page 12). [NH17] Anand Natarajan and Aram W. Harrow.Semidefinite programming and computa- tional aspects of entanglement. Lecture 1: November 3. IHP Fa...

    work page Pith review arXiv 1987

  2. [1236]

    Com- puting linear sections of varieties: quantum entanglement, tensor decompo- sitions and beyond

    DOI: 10 .1145/ 3313276 . 3316299. arXiv: 1808 .07226 [cs.LG] . URL: https : //doi.org/10.1145/3313276.3316299 (pages 3, 9). [JLV23] Nathaniel Johnston, Benjamin Lovitz, and Aravindan Vijayaraghavan. “Com- puting linear sections of varieties: quantum entanglement, tensor decompo- sitions and beyond”. In: 2023 IEEE 64th Annual Symposium on Foundations of Co...

    work page arXiv 2021

  3. [2026]

    Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding

    DOI: 10.48550/arXiv.2604.22699 . arXiv: 2604.22699 [cs.DS] . URL: https: //arxiv.org/abs/2604.22699 (pages 3, 9). [ABMT25] Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, and Stefan Tiegel. “Sample- Optimal Private Regression in Polynomial Time”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing . STOC ’25. Prague, Czechia: Associat...

    work page Pith review arXiv doi:10.48550/arxiv.2604.22699 2012

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.