  We pose a generalized Boson Sampling problem. Strong evidence exists that
such a problem becomes intractable on a classical computer as a function of the
number of Bosons. We describe a quantum optical processor that can solve this
problem efficiently based on Gaussian input states, a linear optical network
and non-adaptive photon counting measurements. All the elements required to
build such a processor currently exist. The demonstration of such a device
would provide the first empirical evidence that quantum computers can indeed
outperform classical computers and could lead to applications.
