Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

Understand

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n*n matrix A.

• The algorithm runs in O(n^2/eps^2) time, and approximates Per(A) to within eps*||A||^n additive error.
• A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices.
• This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role.