Classical Simulation of Boson Sampling Based on Graph Structure

Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In this Letter, we present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit. The algorithms’ complexity grows as so-called treewidth, which is closely related to the connectivity of a given linear-optical circuit. Using the algorithms, we study approximated simulations for local Haar-random linear-optical circuits. For equally spaced initial sources, we show that, when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error. Notably, right after this depth, photons start to interfere each other and the algorithms’ complexity becomes subexponential in the number of sources, implying that there is a sharp transition of its complexity. Finally, when a circuit is sufficiently deep enough for photons to typically propagate to all modes, the complexity becomes exponential as generic sampling algorithms. We numerically implement a likelihood test with a recent Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.

Figure 1

(a) Input (red dots) and output (blue dots) photon configuration, corresponding bipartite and symmetric graphs, and their tree decompositions of width $w=2$. (b) Graph and its possible tree decomposition of width $w=3$.

Figure 2

Initial state in (a) 1D and (c) 2D architectures. Red dots represent sources. ${\mathcal{L}}_{\alpha }$ represents a sublattice having a single source $s_{\alpha }$. Beam-splitter arrays in (b) 1D and (d) 2D architecture. A single round consists of four steps (1)–(4). The structure can be generalized for $d$-dimensional architecture, where a single round consists of $2d$ steps.

Figure 3

GBS on 2D lattice with $N=36$, $M=N^2$, and $\gamma =2$. (a) Red dots represent initial sources. The black solid line describes the region at which a particular input photon can typically propagate for $D=\mathrm{\Theta }(L^{2(1-\epsilon )})=\mathrm{\Theta }(N^{1-\epsilon })$. (b) Possible tree decomposition of the symmetric graph $B_{\mathit{m}}$ when outputs are at the same position with input sources. An upper bound on the treewidth is $\mathrm{\Theta }(\sqrt{N})$ as shown: the first bag (blue) and the second one (yellow).

Figure 4

The complexity diagram for local Haar-random BS. As the star marks, a sharp transition occurs for the complexity of our algorithm. Easiness for any circuits (asterisk symbol) is proved in Ref. [63]. Note that, for 1D, the depth that is easy for typical circuits is larger (see Theorem 3).

Figure 5

Likelihood test for the recent GBS experiment [10]. (a) Rearranged mode configuration with squeezed states sources (red dots). For approximated sampling, we discard elements of a circuit matrix $U$ that is farther than $K$ for the sources. (b) Log-likelihood ratio of experimental samples against those from the treewidth algorithm.