Quantum Separability in Polynomial Time

The central problem in quantum information theory addressed here is the quantum separability problem: given a bipartite density matrix, determine whether it is separable (a convex combination of product states) or if it is at least η-far from every separable state in the Euclidean norm. While this problem is known to be NP-hard in the general case, this paper seeks a polynomial-time algorithm for the constant-error regime.

The author develops a randomized algorithm that leverages a connection between the separability problem and the optimization of a support function over product states. The technical core involves decomposing a Hermitian matrix into a flat component and a small tail component using Haar-random unitaries. By showing that flat matrices possess near-optimal solutions that are also flat (i.e., have small entrywise coefficients), the author reduces the continuous optimization problem to a discrete constraint satisfaction problem (CSP). This discretized problem is then solved using a dense-CSP polynomial-time approximation scheme (PTAS).

The paper provides a randomized algorithm that runs in time polynomial in the dimension d for any fixed constant gap η > 0. This algorithm successfully distinguishes between separable states and those that are η-far from the set of separable states. Beyond the membership problem, the algorithm also provides a polynomial-time solution for the Best Separable State (BSS) problem for specific classes of operators and improves the complexity of computing ground-state energies for mean-field Hamiltonians from quasi-polynomial to polynomial time.

This result is a significant milestone in quantum information theory, as it closes a long-standing gap regarding the computational complexity of detecting entanglement. By demonstrating that the constant-gap Euclidean weak-membership problem is in P, the paper provides a powerful tool for analyzing quantum systems and offers a new algorithmic framework that may be applicable to other problems involving high-dimensional tensor products.