What can quantum optics say about computational complexity theory?

Saleh Rahimi-Keshari, Austin P. Lund, Timothy C. Ralph

Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain results that are of in…