Bad Qubits — Learn Quantum by Doing

Multiple choice

In boson sampling, the collision-free output amplitudes are permanents of n-by-n submatrices of the interferometer unitary. Why does this make sampling classically hard, whereas the analogous determinant-based problem would be easy?

The permanent requires entangling gates to evaluate, while the determinant does not
The permanent is only defined for matrices larger than the determinant
The determinant is #P-complete, while the permanent is in P
Computing the permanent of a 0/1 matrix is #P-complete, while the determinant is computable in polynomial time by Gaussian elimination