  Sampling from probability distributions of quantum circuits is a
fundamentally and practically important task which can be used to demonstrate
quantum supremacy using noisy intermediate-scale quantum devices. In the
present work, we examine classical simulability of sampling from the output
photon-number distribution of linear-optical circuits composed of random beam
splitters with equally distributed squeezed vacuum states and single-photon
states input. We provide efficient classical algorithms to simulate
linear-optical random circuits and show that the algorithms' error is
exponentially small up to a depth less than quadratic in the distance between
sources using a classical random walk behavior of random linear-optical
circuits. Notably, the average-case depth allowing an efficient classical
simulation is larger than the worst-case depth limit, which is linear in the
distance. Besides, our results together with the hardness of boson sampling
give a lower-bound on the depth for constituting global Haar-random unitary
circuits.
