  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 interest from both quantum theory and the
computational complexity theory point of view. We derive a general formula for
calculating the output probabilities, and by considering input thermal states,
we show that the output probabilities are proportional to permanents of
positive-semidefinite Hermitian matrices. It is believed that approximating
permanents of complex matrices in general is a #P-hard problem. However, we
show that these permanents can be approximated with an algorithm in BPP^NP
complexity class, as there exists an efficient classical algorithm for sampling
from the output probability distribution. We further consider input
squeezed-vacuum states and discuss the complexity of sampling from the
probability distribution at the output.

Quantum Physics;Computational Complexity