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.
展开▼
机译：J. Edmonds概括了二部完全匹配的决策问题，在[14]中引入了确定 M（N）的给定线性子空间是否包含非奇异矩阵的问题（现在称为Edmonds问题） ，其中 M（N）表示复数 N x N 矩阵的线性空间。这个问题导致了拟阵理论等方面的许多根本发展。经典匹配理论可以用具有非负项的矩阵来定义。量子理论中心的正算符概念是具有非负项的矩阵的自然概括。 （此处的算子是指从矩阵到矩阵的映射。）首先，我们用完全正算子或等效地用二分密度矩阵来重新表示Edmonds问题。事实证明，可以在多项式确定时间内解决爱德蒙兹问题的最重要情况之一，即两个几何拟阵的交集对应于无纠缠（又是可分离的）二分密度矩阵。我们介绍了 M（N）的线性子空间的非常通用的类（或承诺），在该类上存在用于解决Edmonds问题的多项式确定性时间算法。该算法是[23]，[26]中算法的全面概括，其分析得益于永久物的算子类似物，即所谓的量子永久物。最后，我们证明了可分离归一化二部密度矩阵的凸集的弱隶属度问题是NP-HARD。
展开▼
