Nullstellensatz-Inspired Algorithms for Certifying Entanglement of Subspaces

Explore a 56-minute lecture on Nullstellensatz-inspired algorithms for certifying entanglement of subspaces, presented by Benjamin Lovitz at the Centre de recherches mathématiques (CRM) Workshop on Tensors: Quantum Information, Complexity and Combinatorics. Delve into the computational primitive of determining whether a given linear subspace of pure states contains product states, and learn about the applications of certifying entanglement in subspaces. Discover how degree-2 Nullstellensatz certificates can efficiently certify entanglement in generic subspaces, despite the exponential scaling of worst-case algorithms. Examine a robust variant of this primitive and the development of a hierarchy of eigenvalue computations for determining the Hausdorff distance between a subspace and product states. Explore an algorithm inspired by Nullstellensatz certificates for finding product elements in subspaces under genericity conditions, leading to new approaches for tensor rank decompositions. Investigate the generalization of these techniques to arbitrary varieties and their extension to varieties over real numbers. Gain insights into joint work with Nathaniel Johnston and Aravindan Vijayaraghavan, covering topics such as the Segre variety, robust versions of algorithms, and polynomial-time computations in quantum information theory.

Introduction
Question
Applications
Computing the distance
Finding elements of the intersection
Varieties
Algorithm
General statement
Input
Motions
Polynomial time
Robust version