Abstract
I will first explain the importance of the permanent of PSD matrices in Quantum Linear Optics, and put it into more general concept of so called quantum permanent of bipartite density matrices.
In this talk I will show how to get a c^n approximation algorithm for the permanent of PSD matrices, where c is a universal constant (prior to this result not even randomized poly-time algorithm with (even) worst case simply exponential relative error was known); and e^n approximation algorithm for the quantum permanent of separable, aka non-entangled, bipartite density matrices.
Our algorithm is based on a semidefinite program with a convex nonlinear objective. Our proof of its correctness is essentially a New Van Der Waerden Like Lower Bound: What is the smallest value of the permanent of projectors on images of n × n correlation matrices?
If time permits, I will talk about how our result can “save” the recently refuted permanent-on-top conjecture as well as its application to approximating the largest eigen-value of certain n! × n! PSD matrices.
Based on the joint work with Nima Anari, Shayan Oveis Gharan, Amin Saberi.