  Boson Sampling is a task that is conjectured to be computationally hard for a
classical computer, but which can be efficiently solved by linear-optical
interferometers with Fock state inputs. Significant advances have been reported
in the last few years, with demonstrations of small- and medium-scale devices,
as well as implementations of variants such as Gaussian Boson Sampling. Besides
the relevance of this class of computational models in the quest for
unambiguous experimental demonstrations of quantum advantage, recent results
have also proposed first applications for hybrid quantum computing. Here, we
introduce the adoption of non-linear photon-photon interactions in the Boson
Sampling framework, and analyze the enhancement in complexity via an explicit
linear-optical simulation scheme. By extending the computational expressivity
of Boson Sampling, the introduction of non-linearities promises to disclose
novel functionalities for this class of quantum devices. Hence, our results are
expected to lead to new applications of near-term, restricted photonic quantum
computers.
