Laplace expansions and tree decompositions: A faster polytime algorithm for shallow nearest-neighbor boson sampling
Open Access
- 16 March 2026
- journal article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 113 (3)
Abstract
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.Keywords
All Related Versions
Funding Information
- Engineering and Physical Sciences Research Council
This publication has 17 references indexed in Scilit:
- Exploring shallow-depth boson sampling: Toward a scalable quantum advantagePhysical Review A, 2024
- Efficient sampling from shallow Gaussian quantum-optical circuits with local interactionsPhysical Review A, 2022
- Further compactifying linear optical unitariesAPL Photonics, 2021
- Quantum simulation of partially distinguishable boson samplingPhysical Review A, 2018
- An efficient tree decomposition method for permanents and mixed discriminantsLinear Algebra and its Applications, 2016
- The permanent of a square matrixEuropean Journal of Combinatorics, 2010
- Introduction to Optical Quantum Information Processing2010
- Quantum-mechanical lossless beam splitter: SU(2) symmetry and photon statisticsPhysical Review A, 1989
- The complexity of computing the permanentTheoretical Computer Science, 1979
- New fast method for generating discrete random numbers with arbitrary frequency distributionsElectronics Letters, 1974