  Boson sampling can simulate physical problems for which classical simulations
are inefficient. However, not all problems simulated by boson sampling are
classically intractable. We consider a situation in which it is known that the
outcome from boson sampling is sparse. It can be determined from a few marginal
distributions which are classically calculable. Still, recovering of the joint
distribution can be of high complexity. We show classically efficient methods
of the recovery assuming high sparsity of the joint distribution. Various
extensions are discussed including a version involving quantum annealing.
