A Poly-Time Deterministic Algorithm for Simply Exponential Approximation of the Permanent of PSD and Other Cool Quantum Things
Leonid GurvitsProfessor in the Computer Science Department at the City University of New York
Faculty Host:Alex Olshevsky
Refreshments at 10:45am
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 eigenvalue of certain n! × n! PSD matrices.
Bio:Leonid Gurvits was born in Soviet (aka Northern) Bukovina and lived there until the end of 1989. He started American life in 1990, in Brooklyn. He has worked in many areas and at many places, as academic as well industrial, but never at Wall Street. He spent the longest, and the most creative, stint at Los Alamos National Lab when it still was a great scientific institution. Since 2013, L.G. is a professor at the City College of New York.
Leonid is the founder of the "hyperbolic polynomials approach" to combinatorics, geometry, counting and discrete math in general. One of his proofs
has been recently included, as a new chapter, to the latest edition of "Proofs from the Book".