Constant trace-distance separability testing

Unsolved ID op_ec184fc49232a9c0 Last edited 4 September 2026

Edit

Fields: Quantum algorithm
Quantum Resource Theory
Topics: Quantum separability
Computational complexity and computability

Problem

What is the computational complexity of testing bipartite separability with a constant trace-distance promise gap? For local dimension \(d\), define

\begin{equation} \operatorname{Sep}(d,d) :=\operatorname{conv}\!\left\{ \alpha\otimes\beta: \alpha,\beta\in\mathcal D(\mathbb C^d) \right\}. \tag{1} \end{equation}

Fix a constant \(0<\varepsilon_0<1\). Given a rational description of \(\rho\in\mathcal D(\mathbb C^d\otimes\mathbb C^d)\), promised that exactly one of the following alternatives holds,

\begin{equation} \begin{aligned} \text{YES:}\quad&\rho\in\operatorname{Sep}(d,d),\\ \text{NO:}\quad& \inf_{\sigma\in\operatorname{Sep}(d,d)} \frac12\lVert\rho-\sigma\rVert_1\geq\varepsilon_0, \end{aligned} \tag{2} \end{equation}

decide which case in Eq. (2) holds. Is there an algorithm polynomial or quasipolynomial in \(d\)? More generally, when the gap \(\varepsilon\) is part of the input, determine the optimal dependence of the complexity on \(d\) and \(\varepsilon\).

Source

Harrow and Montanaro explicitly pose constant-gap weak membership for separability in trace norm as an open complexity problem [HM13].

Progress

Harrow and Montanaro formulate the constant trace-distance promise in Eq. (2) explicitly and relate it to estimating acceptance probabilities in \(\mathsf{QMA}(2)\) [HM13].
Weak membership for the set in Eq. (1) is strongly \(\mathsf{NP}\)-hard when the promised distance is inverse-polynomial in the input dimension [Gha10]. This hardness regime does not classify the fixed constant gap in Eq. (2).
A symmetric-extension algorithm has running time

\begin{equation} \exp\!\left( O\!\left(\varepsilon^{-2}(\log d)^2\right) \right) \tag{3} \end{equation}

for Euclidean distance or an operational \(\mathsf{LOCC}\) norm [BCY11]. The bound in Eq. (3) does not hold as stated for trace distance.
For each fixed constant gap, randomized polynomial time is now known for Euclidean-norm weak membership [Mal26]. Constant trace distance can coexist with Euclidean distance that vanishes with \(d\), so this result does not solve Eq. (2).

Comment

The constant-gap trace-norm task in Eq. (2) is posed explicitly in Section 4.2, item 14 of [HM13]. The norm is essential: the constant-gap Euclidean problem has been solved, but that result does not classify trace-norm weak membership.

References

[HM13]: A. W. Harrow and A. Montanaro, “Testing Product States, Quantum Merlin–Arthur Games and Tensor Optimization,” Journal of the ACM 60, Article 3 (2013).DOI arXiv
[Gha10]: S. Gharibian, “Strong NP-Hardness of the Quantum Separability Problem,” Quantum Information and Computation 10, 343–360 (2010).arXiv
[BCY11]: F. G. S. L. Brandão, M. Christandl, and J. Yard, “A Quasipolynomial-Time Algorithm for the Quantum Separability Problem,” in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 343–351 (2011).DOI arXiv
[Mal26]: G. Malavolta, “Quantum Separability in Polynomial Time,” arXiv:2607.23773 (2026).arXiv

Constant trace-distance separability testing

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems