  Experimental demonstration of the quantum advantage over classical
simulations with Boson Sampling is currently under intensive investigation.
There seems to be a scalability issue to the necessary number of bosons on the
linear optical platforms and the experiments, such as the recent Boson Sampling
with $20$ photons on $60$-port interferometer by H.~Wang~\textit{et al},
\textit{Phys. Rev. Lett.} \textbf{123,} 250503 (2019), are usually carried out
on a small interferometer, much smaller than the size necessary for the
no-collision regime. Before demonstration of quantum advantage, it is urgent to
estimate exactly how the classical computations necessary for sampling from the
output distribution of Boson Sampling are reduced when a smaller-size
interferometer is used. The present work supplies such a result, valid with
arbitrarily close to $1$ probability, which reduces in the no-collision regime
to the previous estimate by P.~Clifford and R.~Clifford. One of the results
with immediate application to current experiments with Boson Sampling is that
classically sampling from the interference of $N$ single bosons on an $M$-port
interferometer is at least as hard as that with $\mathcal{N}= \frac{N}{1+N/M}$
single bosons in the no-collision regime, i.e., on a much larger interferometer
with at least $\mathcal{M}\gg N^2$ ports.
