Best Separable State beyond perfect completeness

The paper’s subexponential algorithm needs the YES case to be exact — whether that promise can be relaxed to a constant gap is the first question the paper leaves open.

Motivation

The Best Separable State problem \(\mathrm{BSS}_{c,s}\) — distinguish, given a quantum measurement, whether some non-entangled state passes with probability at least \(c\) or every non-entangled state fails to reach \(s\) — is the algorithmic face of \(\mathsf{QMA}(2)\): a quasi-polynomial algorithm for \(\mathrm{BSS}_{0.99,0.5}\) would place \(\mathsf{QMA}(2) \subseteq \mathsf{EXP}\). It is also how entanglement witnesses are certified experimentally, which is inherently a noisy, two-sided-error task.

Barak, Kothari and Steurer’s \(2^{\tilde O(\sqrt n)}\)-time algorithm — the first to beat brute force for general measurements — solves \(\mathrm{BSS}_{1,s}\): the YES case must be exact. That promise is fragile in exactly the setting (noisy entanglement witnesses) that motivates the problem, and Remark 1.4 of the paper conjectures the algorithm survives replacing it with any constant completeness error. This hub tracks that question, and the near-perfect-completeness case the paper actually proves along the way.

Provenance and history

Boaz Barak, Pravesh K. Kothari and David Steurer, Quantum entanglement, sum of squares, and the log rank conjecture, STOC 2017; arXiv:1701.06321v2, 9 July 2017. Remark 1.4 states the conjecture; Theorem 1.3 is the \(c=1\) result being extended; Remark 4.3 gives the near-perfect-completeness (\(c = 1-1/n\)) case “for free,” as a consequence of the same rounding analysis. Section 8 re-poses the constant-error question as the first item in the paper’s own list of open problems. The statement was drafted by scripts/harvest_conjectures.py from this PDF and is AI-written and unreviewed, as the status badge says; the draft’s own adversarial check caught a defect (a formal statement requiring a deterministic algorithm where the paper’s own rounding step, Lemma 7.1, is randomized) before publication, verified independently against the source PDF on 19 August 2026.

A closely related but non-resolving result appeared while this statement was being checked: A Simple Algorithm for Best Separable State (arXiv:2608.10147, August 2026) gives a more efficient algorithm, but stays within the perfect-completeness (\(c=1\)) regime and does not address constant completeness error; its own open-questions section asks a different, near-perfect-completeness question instead.

Parameter lattice

The one dimension this hub tracks is the completeness error, crossed against whether a subexponential algorithm is known.

completeness regime subexponential algorithm known?
perfect (\(c=1\)) Yes — Theorem 1.3, \(2^{\tilde O(\sqrt n)}\) time
near-perfect (\(c = 1-1/n\)) Yes — Remark 4.3, same running time, “for free”
constant (\(c\) a fixed constant \(<1\)) open — tracked at c/0049

Nothing published closes the gap of order \(n\) between the near-perfect regime and a constant one, and no partial result at any intermediate error (e.g. \(1/\mathrm{polylog}(n)\)) is reported.

Statements in this hub