Notes on Scott’s 5th and final lecture of the mini-course “Complexity theory and quantum optics”. This lecture was delivered on Dec. 20th, 2013, at UFF.

We start by addressing some loose ends from yesterday:

1- Why does polynomial interpolation not show the #P-hardness of GPE?

Approximating the permanent is hard. For most matrices, exactly calculating the permanent is hard. But for finite fields, there’s an equivalence between worst and average cases. Why doesn’t the idea used for that last proof apply to our case of complex-valued matrices? More concretely, let us suppose we can approximate the permanent of most matrices. Why doesn’t this help us approximate the permanent of any other matrix?

Think of a set $latex M$ of matrices whose permanents we can estimate. Now I have a target matrix, and I would like to use polynomial interpolation to get a good estimate of its permanent by extrapolating the…

View original post 3,158 more words