Scott Aaronson’s mini-course at UFF, 5th (and final) lecture

quantum Rio

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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s