Classical deterministic complexity of Edmonds' Problem and quantum entanglement

Abstract

Generalizing a decision problem for bipartite perfect matching, J. Edmonds introduced in [14] the problem (now known as the Edmonds Problem) of deciding if a given linear subspace of M(N) contains a nonsingular matrix, where M(N) stands for the linear space of complex NxN matrices. This problem led to many fundamental developments in matroid theory etc.Classical matching theory can be defined in terms of matrices with nonnegative entries. The notion of Positive operator, central in Quantum Theory, is a natural generalization of matrices with nonnegative entries. (Here operator refers to maps from matrices to matrices.) First, we reformulate the Edmonds Problem in terms of of completely positive operators, or equivalently, in terms of bipartite density matrices. It turns out that one of the most important cases when Edmonds' problem can be solved in polynomial deterministic time, i.e. an intersection of two geometric matroids, corresponds to unentangled (aka separable) bipartite density matrices. We introduce a very general class (or promise) of linear subspaces of M(N) on which there exists a polynomial deterministic time algorithm to solve Edmonds' problem. The algorithm is a thoroughgoing generalization of algorithms in [23], [26], and its analysis benefits from an operator analog of permanents, so called Quantum Permanents. Finally, we prove that the weak membership problem for the convex set of separable normalized bipartite density matrices is NP-HARD.