Subexponential Best Separable State with Imperfect Completeness
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
The paper’s headline algorithm distinguishes, in time \(2^{\tilde O(\sqrt n)}\), whether some non-entangled state passes a given measurement with certainty or whether every non-entangled state fails it by a constant margin — but the “passes with certainty” side of that promise is fragile, and the paper’s own motivation for the problem (noisy, experimentally realizable entanglement witnesses) lives in the regime where nothing is ever certain. This conjecture is the paper’s own proposal to remove that fragility, and it is the first item in the paper’s list of open questions.
View PDF · LaTeX source · Formal statement — not yet formalized
Let \(\mathcal{M}\) be an \(n^2 \times n^2\) quantum measurement operator (\(0 \preceq \mathcal{M} \preceq I\)). A state \(\rho\) (an \(m \times m\) complex Hermitian, positive semidefinite matrix with \(\operatorname{Tr}\rho = 1\), \(m = n^2\)) is separable if it is a convex combination of pure states \(ww^{*}\) with \(w = uv^{*}\) for unit vectors \(u, v \in \mathbb{C}^n\). The promise problem \(\mathrm{BSS}_{c,s}\) asks to distinguish, given \(\mathcal{M}\), the case that some separable \(\rho\) has \(\operatorname{Tr}(\rho\mathcal{M}) \ge c\) from the case that every separable \(\rho\) has \(\operatorname{Tr}(\rho\mathcal{M}) \le s\).
Conjecture. For all constants \(c, s\) with \(0 \le s < c < 1\) there exist a finite constant \(C = C(c,s)\) and a randomized algorithm \(\mathcal{A}\) that, on input an \(n^2 \times n^2\) measurement operator \(\mathcal{M}\), halts after at most \(2^{\,C\sqrt n (\log n)^{C}}\) steps and decides \(\mathrm{BSS}_{c,s}\) correctly with probability at least \(2/3\).
This is (a formalization of) Remark 1.4’s conjecture that the paper’s main result — proved there only for \(c=1\) — extends to constant completeness error. The algorithm the paper actually gives is randomized, not deterministic: its rounding step (Lemma 7.1) locates the needed direction by showing a random unit vector succeeds with probability \(2^{-O(k)}\), with no derandomization given, so a randomized algorithm at this running time already settles what the paper conjectures.
Sources
- Barak, Kothari, and Steurer. Quantum entanglement, sum of squares, and the log rank conjecture. STOC 2017; arXiv:1701.06321v2, 9 July 2017. Remark 1.4 (p. 5) states the conjecture; Theorem 1.3 (p. 3) is the \(c=1\) result being extended; Remark 4.3 (p. 12) gives the near-perfect-completeness extension; Section 8 (p. 21) re-poses the question as the first item left open; Lemma 7.1 (p. 18) is the randomized rounding step.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open, and the paper takes no position on which way it goes: “it is an interesting open problem to find out whether our results can extend” to constant completeness error (p. 5), and Section 8 restates this as the first of the paper’s open questions without further comment.
What is known. Theorem 1.3 proves the case \(c=1\): a \(2^{\tilde O(\sqrt n)}\)-time algorithm for \(\mathrm{BSS}_{1,s}\) for every constant \(s<1\). Remark 4.3 extends this, for free, to \(c = 1 - 1/n\): the rounding procedure’s output rank-one matrix has norm at least \(k/n\) (for \(k = \tilde O(\sqrt n)\)), so the argument goes through whenever the projection of the true rank-one solution onto the relevant subspace has squared norm at least \(1 - k^2/n^2\) — a completeness error of order \(\tilde O(1/n)\). The paper frames this explicitly as an extension the existing proof affords “for free,” not as evidence of a barrier.
What is missing. Nothing published closes the remaining gap between a \(\tilde O(1/n)\) completeness error and a constant one — a factor of order \(n\). No partial result at any intermediate error (such as \(1/\mathrm{polylog}(n)\)) is reported anywhere in the paper.
What a resolution would need. A positive answer needs a rounding argument that tolerates a completeness error that does not shrink with \(n\) — the current technique’s tolerance is tied to the norm bound \(k/n\) that Remark 4.3 supplies, and nothing in the paper suggests how to decouple the two. A negative answer (a separation between the perfect/near-perfect and constant-error regimes at this running time) would be new: no such separation, or any argument that the analysis cannot be pushed past \(\tilde O(1/n)\), currently exists.
Why it matters. The two-sided-error version of Best Separable State is the version that bears on quantum complexity (a quasi-polynomial algorithm for \(\mathrm{BSS}_{0.99,0.5}\) would place \(\mathsf{QMA}(2) \subseteq \mathsf{EXP}\)) and on practice: the entanglement-witness motivation the paper itself gives for studying \(\mathrm{BSS}\) is inherently noisy, and perfect completeness is not a promise a physical experiment can deliver. Settling this affirmatively gives the first subexponential algorithm for constant-gap \(\mathrm{BSS}\); settling it negatively would show the \(2^{\tilde O(\sqrt n)}\) running time depends essentially on an exact algebraic promise rather than on the geometry of the separable cone, separating the perfect- and constant-completeness problems.
A recent, adjacent, but non-resolving paper. A more efficient algorithm for the perfect-completeness Best Separable State problem appeared in August 2026 (“A Simple Algorithm for Best Separable State,” arXiv:2608.10147) — but it explicitly stays within the \(c=1\) regime the source paper already solved, and its own open-questions section asks a near-perfect-completeness question (distinguishing \(\mathrm{BSS}(\mathcal{M})=1\) from \(\mathrm{BSS}(\mathcal{M}) = 1-n^{-1+\Omega(1)}\) in polynomial time) rather than the constant-completeness-error question this page states. It does not resolve, and does not appear to cite Remark 1.4’s conjecture directly.
Checked against the literature, 2026-08-19. Searched for post-2017 progress on constant-completeness-error Best Separable State and on \(\mathsf{QMA}(2)\) algorithms generally. Found the improvement above (arXiv:2608.10147, August 2026) and confirmed by reading its stated regime and open-questions section directly that it does not extend to constant completeness error. No other candidate resolution was found in this search. This is a targeted check, not an exhaustive literature sweep — the quantum-complexity literature on \(\mathsf{QMA}(2)\) and Best Separable State is active, and a reviewer should search more broadly (in particular for any paper explicitly citing Remark 1.4) before relying on “still open” as of today.