Geometry and matrix analysis
Speaker: Benjamin Lovitz (Northeastern University)
"Nullstellensatz-inspired algorithms for certifying entanglement of subspaces"
Time: 09:30 - 10:30
Room: zoom
In this talk, I will discuss the computational primitive of determining whether a given linear subspace S of pure states contains any product states. If this is not the case, then we say that S is entangled. Certifying that a subspace S is entangled has applications, for example, in certifying entanglement of mixed states (via the range criterion), and constructing entanglement witnesses. One way to certify entanglement in S is via a Nullstellensatz certificate. While a very high degree certificate may be necessary to certify all entangled subspaces, we prove that already the degree-2 certificate (computable in polynomial time) certifies entanglement of generic subspaces of dimension up to a constant multiple of the maximum possible. This is surprising, given that the best-known algorithm for certifying entanglement of a subspace in the worst case scales exponentially in the system size. A robust variant of this primitive, which asks how far S is from product in Hausdorff distance, has similar applications. We develop a robust version of the Nullstellensatz certificate for computing this variant. Specifically, we construct a hierarchy of eigenvalue computations that compute this distance exactly in the limit. Another related problem is to find the product elements contained in S, if any exist. We develop an algorithm, again inspired by the Nullstellensatz certificate, for solving this problem under certain genericity conditions. As a consequence, we obtain new algorithms for tensor rank decompositions that work for generic tensors of bounded rank. The set of product states forms a variety (called the Segre variety), and it is natural to ask whether these techniques generalize to arbitrary varieties. We prove that they do under certain conditions on the variety. We also extend these results to varieties over the real numbers. This talk is based on joint work with Nathaniel Johnston and Aravindan Vijayaraghavan.