Classical simulation of boson sampling using graph structure

Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum advantages using noisy intermediate-scale quantum devices. We study the computational complexity for boson sampling depending on circuit depths. Specifically, we propose a classical algorithm that takes advantage of graph structure of a given circuit and analyze its complexity. A notable property of our algorithm is that its complexity increases exponentially as so-called treewidth of a graph, which is closely related to connectivity of a circuit. Focusing on typical linear optical circuits composed of local random beam splitters, we show that when a linear-optical circuit has a low depth, its outcomes can be characterized by a constant-treewidth graph so that the algorithm can implement the corresponding boson sampling efficiently. We then show that after the threshold for easy sampling, the complexity becomes sub-exponential and finally exponential for sufficiently deep circuits. The latter is consistent with a generic classical boson sampling algorithm. Finally, we numerically implement a validation test with a smaller size of a recent Gaussian boson sampling experiment and show that our algorithm can pass the test for the circuit having limited connectivity.