These are notes for Scott’s 4th lecture, delivered on Thursday, Dec. 19th, 2013 at UFF.

Let’s start with a short review of last lecture’s finale:

Solving exact BosonSampling is classically hard unless PH collapses. Here’s the argument:

1- Estimating $latex |per(X)|^2$ is already $latex \#P$-hard.

2- Given a fast BosonSampling simulator, we’d be able to estimate $latex |per(X)|^2$ in BPP with an NP oracle (using approximate counting).

3- $latex BPP^{NP} \subseteq NP^{NP^{NP}}$ (Sipser, Gacs, Lautemann).

4- $latex PH \subseteq P^{\#P}$ (Toda’s theorem).

Conclusion: exact BosonSampling must be classically hard unless $latex PH=NP^{NP^{NP}}$, i.e. there’s a collapse in the polynomial hierarchy.

Now we give a second argument for hardness of simulation of exact BosonSampling, this time using the concept of post-selection. This came out of independent work by Bremner, Jozsa and Shepherd, who studied the IQP model, which describes a different type of restricted quantum computer, also believed to be…

View original post 2,640 more words