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.

REFERENCES

• 1: D. Zeilberger, CHu's 1303 identity implies Bombieri's 1990 norm-inequality {Via an identity of Beauzamy and Degot}, Amer. Math. Monthly, 1994.
• 2: B. Beauzamy, E. Bombieri, P. Enflo, H.L. Montgomery, Products of polynomials in many variables, Journal of Number Theory 36, 219--245, 1990.
• 3: B. Reznick, An inequality for products of polynomials, Proc. of AMS, vol. 117, Is. 4, 1063--1073, 1993.
• 4: Bernard Beauzamy, Products of polynomials and a priori estimates for coefficients in polynomial decompositions: a sharp result, Journal of Symbolic Computation, v.13 n.5, p.463-472, May 1992
• 5: A. Nemirovski, Personal Communication, 2001.
• 6: V. Kabanets and R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Electronic Colloq. on Comp. Complex, No. 55, 2002.
• 7: L. Gurvits, Quantum Matching Theory (with new complexity-theoretic, combinatorial and topological insights on the nature of the Quantum Entanglement), arXiv.org preprint quant-ph/02010222, 2002.
• 8: L. Gurvits, Classical deterministic complexity of Edmonds' problem and Quantum Entanglement, arXiv.org preprint quant-ph/0303055, 2003.
• 9: L. Gurvits, Unbiased nonnegative valued random estimator for permanents of complex positive semidefinite matrices, LANL unclassified report LAUR 02-5166, 2002.
• 10: H. Minc, Permanents, Addison - Wesley, Reading, MA, 1978.
• 11: R. B. Bapat, Mixed discriminants of positive semidefinite matrices, Linear Algebra and its Applications 126, 107--124, 1989.
• 12: A. Ben-Tal , A. Nemirovski, Robust Convex Optimization, Mathematics of Operations Research, v.23 n.4, p.769-805, Nov. 1998 [doi>10.1287/moor.23.4.769]
• 13: D. B. Yudin and A. S. Nemirovskii, Informational complexity and efficient methods for the solution of convex extremal problems (in Russian), Ekonomica i Matematicheskie Metody 12 (1976), 357--369.
• 14: J. Edmonds, System of distinct representatives and linear algebra, Journal of Research of the National Bureau of Standards 718, 4(1967), 242--245.
• 15: Alexander Chistov , Gábor Ivanyos , Marek Karpinski, Polynomial time algorithms for modules over finite dimensional algebras, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.68-74, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258751]
• 16: A. I. Barvinok, Computing Mixed Discriminants, Mixed Volumes, and Permanents, Discrete & Computational Geometry, 18 (1997), 205--237.
• 17: Alexander Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures & Algorithms, v.14 n.1, p.29-61, Jan. 1999 [doi>10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X]
• 18: G. P. Egorychev, The solution of van der Waerden's problem for permanents, Advances in Math., 42, 299--305, 1981.
• 19: D. I. Falikman, Proof of the van der Waerden's conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29, 6: 931-938, 957, 1981, (in Russian).
• 20: M. Grötschel, L. Lovasz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988.
• 21: L. Gurvits, Van der Waerden Conjecture for Mixed Discriminants, submitted, 2000; accepted for publication in Advances in Mathematics, 2001.
• 22: A. Zvonkin, Matrix integral and map enumeration : an accessible introduction, Mathl. Comput. Modelling, Vol. 26, No. 8-10, pp. 281--304, 1997.
• 23: Nathan Linial , Alex Samorodnitsky , Avi Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.644-652, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276880]
• 24: Leonid Gurvits , Alex Samorodnitsky, A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.48-57, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335311]
• 25: L. Gurvits and A. Samorodnitsky, A deterministic algorithm approximating the mixed discriminant and mixed volume, and a combinatorial corollary, Discrete Comput. Geom. 27 : 531--550, 2002 /
• 26: L. Gurvits and P. Yianilos, The deflation-inflation method for certain semidefinite programming and maximum determinant completion problems, NECI technical report, 1998.
• 27: Jurgen Forster, A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity, Proceedings of the 16th Annual Conference on Computational Complexity, p.100, June 18-21, 2001
• 28: L. Gurvits and H. Barnum, Largest separable balls around the maximally mixed bipartite quantum state," Phys. Rev. A 66 062311 (2002).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory