Laplace expansions and tree decompositions: A faster polytime algorithm for shallow nearest-neighbor boson sampling
Samo Novák, Raúl García−Patrón · Physical Review A · 2026
In a boson sampling quantum optical experiment, we send n individual photons into an m -mode interferometer and measure the occupation pattern on the output. The statistics of this process depend on the permanent of a matrix representing the experiment, which is itself a #P-hard problem to compute, and this is the reason why ideal and fully general boson sampling is hard to simulate on a classical computer. We exploit the fact that, for a nearest-neighbor shallow circuit, i.e., depth D = O ( log m ) , one can adapt the algorithm by Clifford and Clifford [SODA '18 (2018), pp. 146–155] to exploit the sparsity of the shallow interferometer using an algorithm by Cifuentes and Parrilo [] that can efficiently compute a permanent of a structured matrix from a tree decomposition. Our algorithm generates a sample from a shallow circuit in time O ( n 2 2 ω ω 2 ) + O ( ω n 3 ) , where ω is the treewidth of the decomposition that satisfies ω ≤ 2 D for nearest-neighbor shallow circuits. The key difference in our work with respect to previous work using similar methods is the reuse of the structure of the tree decomposition, allowing us to adapt the Laplace expansion used by Clifford and Clifford, which removes a significant factor of m from the running time, especially as m > n 2 is a requirement of the original boson sampling proposal.