Classical complexity and quantum entanglement
type: Item
instance of: scholarly article
title: Classical complexity and quantum entanglement
zbMATH Open document ID: 1093.81012
author: Leonid Gurvits
published in: Journal of Computer and System Sciences
publication date: 2004-11-18T00:00:00Z
review text: 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 probl…
Mathematics Subject Classification ID: 81P68
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 15A22
zbMATH DE Number: 2116232
zbMATH Keywords: Edmonds problem
zbMATH Keywords: entaglement
reviewed by: Vladik Kreinovich
MaRDI profile type: Publication
full work available at URL: j.jcss.2004.06.003
OpenAlex ID: W1966991151
cites work: Mixed discriminants of positive semidefinite matrices
cites work: Computing mixed discriminants, mixed volumes, and permanents
cites work: Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
cites work: Products of polynomials and a priori estimates for coefficients in polynomial decompositions: A sharp result
cites work: Products of polynomials in many variables
cites work: Robust convex optimization
cites work: Q4226940
cites work: Completely positive linear maps on complex matrices
cites work: Systems of distinct representatives and linear algebra
cites work: The solution of van der Waerden's problem for permanents
cites work: Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
cites work: Geometric algorithms and combinatorial optimization
cites work: Classical deterministic complexity of Edmonds' Problem and quantum entanglement
cites work: A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
cites work: A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
cites work: Permanents
cites work: An Inequality for Products of Polynomials
cites work: The rate of convergence of Sinkhorn balancing
cites work: Q4097094
cites work: Chu's 1303 Identity Implies Bombieri's 1990 Norm-Inequality (Via an Identity of Beauzamy and Degot)
cites work: Matrix integrals and map enumeration: an accessible introduction
Wikidata QID: Q59620091
DOI: 10.1016/J.JCSS.2004.06.003
description: scientific article; zbMATH DE number 2116232