Classical complexity and quantum entanglement (Q1886316)

The Edmonds problem is, given \(k\leq n^2\) square \(n\times n\) matrices \(A_1,\ldots,A_k\), to check whether there exists a non-singular linear combination \(\sum x_i A_i\). If such a combination exists, then \(\det(\sum x_i A_i)\neq 0\) for almost all \(x_i\). So, in principle, we can solve the Edmonds problem fast by checking whether for random \(x_i\), the combination is non-degenerate. An important open question is whether we can solve the Edmonds problem in deterministic polynomial time. The only known deterministic algorithms that solve all instance of this problem require exponential time. For example, we can explicitly express the polynomial \(\det(\sum x_i A_i)\) as a linear combination of monomials \(\sum a_{r_1,\ldots,r_k} x_1^{r_1}\ldots x_k^{r_k}\) and check whether all the coefficients \(a_{r_1,\ldots,r_k}\) are 0; since there are exponentially many coefficients, we thus need exponential time. There are cases for which the Edmonds problem can be efficiently solved. The author describes a new reasonably general case for which a deterministic polynomial-time algorithm is possible. His algorithm uses ideas from recent algorithms for bipartite perfect matching -- the problem whose generalization leads to the original formulation of the Edmonds problem; in effect, the algorithm computes the value \(| a_{r_1,\ldots,r_k}| ^2\cdot r_1!\cdot \ldots \cdot r_k!\) -- that is different from 0 if and only if there exists a non-singular linear combination. The author shows that the Edmonds problem can be naturally reformulated in terms of bipartite density matrices -- matrices that describe states of 2-component quantum systems. He also shows that the cases when a deterministic polynomial-time algorithm is possible include the physically interesting case of unentangled (= separable) bipartite states. This efficiency result is very interesting because the author also proves that for convex sets of separable normalized bipartite density matrices, the membership problem is NP-hard.