Classical deterministic complexity of Edmonds' Problem and quantum entanglement

By Leonid Gurvits. Symposium on the Theory of Computing, 2003

509 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/64884dc8b411b18a9d8513d0bb02c176a6238aa4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Statistics and Probability

Citations in the corpus

A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps (2016, methodology): “The fact that fully indecomposable matrices are uniquely scalable was first proved in Gurvits 2003.”
The Theory of Quantum Information (2018, result): “In general, it is likely to be a computationally difficult task to test a bipartite density operator for separability, as suggested by the hardness result proved by Gurvits [82].”
Most Tensor Problems Are NP-Hard (2009, unknown): “is identically the zero polynomial [Gurvits 2003].”
Random matrix techniques in quantum information theory (2015, background): “ with the set of separable states are usually very dicult. 4.4. Entanglement criteria. The question whether a given mixed quantum state is separable or entangled has been proven to be an NP-hard one [Gur03]. To circumvent this worse-case intractability, entanglement criteria are used. These are ecie”
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods (2017, methodology): “This procedure has been repeatedly used since as early as 1937 in a number of diverse areas, such as telecommunication [21], engineering [13], statistics [22], [10], machine learning [23], and even computational complexity [24], [25].”
Entanglement certification from theory to experiment (2018, background): “[61] Leonid Gurvits, “Classical Deterministic Complexity of Edmonds’ Problem and Quantum Entanglement,” in Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing , STOC ’03 (ACM, New York, NY, USA, 2003) pp.”
Entanglement detection (2008, background): “It has been shown that the separability problem, considered as a weak membership problem, is an NP hard problem [105].”
The Church of the Symmetric Subspace (2013, methodology): “The set of separable density matrices (i.e. the convex hull of | α (cid:105) (cid:104) α | ⊗ | β (cid:105) (cid:104) β | ) is notoriously hard to approximate [22, 6], so we are forced to use heuristics and relaxations.”