Abstract
Noncommutative polynomial optimization (NPO) studies the problem of minimizing polynomials of noncommuting variables subject to non-trivial polynomial constraints. Such variables must be understood as operators acting on a not-a-priori-defined Hilbert space. In this talk I will introduce a practical hierarchy of SDP relaxations to solve NPO problems with dimension constraints. In those problems, the space where the noncommuting variables act is restricted to have a dimension below a threshold, defined by the user. Dimension constrained NPO problems appear naturally in quantum information theory and convex optimization (one such famous problem is the computation of the SDP rank of a positive matrix). I will argue that, for any dimension threshold, the new hierarchy can be run with exponentially fewer resources than the unconstrained one. Finally, I will discuss the efficiency of the new hierarchy by applying it to solve a number of NPO problems which were previously thought to be intractable in a normal desktop. Joint work with T. Vértesi and A. Winter.