Laplace expansions and tree decompositions: A faster polytime algorithm for shallow nearest-neighbour Boson Sampling

Samo Novák, Raúl García-Patrón · 2024

Read Laplace expansions and tree decompositions: A faster polytime algorithm for shallow nearest-neighbour Boson Sampling by Samo Novák, Raúl García-Patrón (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18664.txt.

Introduction

Samo Novák and Raúl García-Patrón speed up a classical simulation of a quantum optics experiment in a 2024 paper. In such an experiment, single photons pass through a network and their output patterns follow a hard matrix value called the permanent.

That hardness is why the experiment is thought to beat classical machines. For a shallow network where light only travels between neighbors, the sparsity of the setup can be exploited. The authors adapt an older algorithm using a method that computes permanents of structured matrices from a tree split of the problem. Reusing that tree structure across the computation removes a large factor from the running time. The gain grows when the mode count far exceeds the photon count.

Catalog record

CREATORSamo Novák, Raúl García-Patrón
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-18664

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Laplace expansions and tree decompositions: A faster polytime algorithm for shallow nearest-neighbour Boson Sampling Samo Novák, Raúl García-Patrón Abstract In a Boson Sampling quantum optical experiment we send n n individual photons into an m m -mode interferometer and we measure the occupation pattern on the output. The statistics of this process depending on the permanent of a matrix representing the experiment, a #P-hard problem to compute, is the reason behind ideal and fully general Boson Sampling being hard to simulate on a classical computer. We exploit the fact that for a nearest-neighbour shallow circuit, i.e. depth D = 𝒪 ⁡ ( log ⁡ m ) D=\mathcal{O}(\log m) , one can adapt the algorithm by Clifford & Clifford [ 1 ] to exploit the sparsity of the shallow interferometer using an algorithm by Cifuentes & Parrilo [ 2 ] 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 𝒪 ⁡ ( n 2 ​ 2 ω ​ ω 2 ) + 𝒪 ⁡ ( ω ​ n 3 ) \mathcal{O}(n^{2}2^{\omega}\omega^{2})+\mathcal{O}(\omega n^{3}) , where ω \omega is the treewidth of the decomposition which satisfies ω ≤ 2 ​ D \omega\leq 2D for nearest-neighbour 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 & Clifford which removes a significant factor of m m from the running time, especially as m > n 2 m>n^{2} is a requirement of the original Boson Sampling proposal. 1 1 1 Accepted in PRA on 6 February 2026 as https://doi.org/10.1103/l4zf-ls9v . I Introduction Figure 1: Overview of our work using an example: (a) The shallow brickwork circuit of nearest-neighbour beamsplitters with inputs on right and outputs on the left, showing one measurement outcome with previously sampled photons “ \bullet ” and a new photon “ \bullet^{*} ” added in this step of the Clifford and Clifford algorithm to expand the sample. (b) A weighted bipartite graph represents the outcome: vertices are input and output photons, and non-zero transition amplitudes between them give weighted edges. The outcome amplitude is the sum of weighted perfect matchings in this graph, i.e. the permanent. (c) To exploit the sparsity structure, we construct a tree decomposition : a tree whose nodes contain sets of edges of the graph in (b), subject to simple rules. We use a linear decomposition (no branching) where each node corresponds uniquely to an input photon vertex. We then modify the tree decomposition in several steps, each time temporarily removing a different input photon = column = node of the tree, replacing the latter by a dummy with no new information, seen in (d) . Permanents of these modified trees form the Laplace expansion , our main technical contribution. When done in the right order, conceptualized as a “machine head” walking the tree from one end to the other, we can reuse most of the dynamic programming tables required by the Cifuentes and Parrilo permanent algorithm. As seen in the middle term, we note that the dummy may need to be nonempty. Boson Sampling was introduced by Aaronson & Arkhipov [ 3 ] in 2010 to propose a suitable candidate for the experimental demonstration of quantum advantage , which is when a quantum computer can efficiently solve a problem that a classical computer cannot [ 4 ] . Boson Sampling consists of sending n fully indistinguishable photons through an interferometer acting on m modes, and detecting the photons as they come out at the output of the interferometer. The work by Aaronson and Arkhipov provided strong evidence that such a quantum optics circuit would be hard to simulate on a classical computer when the interferometer was chosen at random from the Haar ensemble. The intuition behind the hardness of Boson Sampling relies in the fact that its output probabilities require computing permanents of matrices that scale with the number of photons in the interferometer. The permanent of a matrix A\in\mathbb{C}^{n\times n} is defined as \per A=\sum_{\sigma\in\mathrm{S}_{n}}\prod_{i=1}^{n}A_{i,\sigma(i)}, where \sigma is a permutation from the symmetric group on n elements \mathrm{S}_{n} . Despite its similarity with the definition of the determinant (without switching signs), computing the permanent exactly or approximating it for matrices with complex entries is #P-hard [ 5 ] . The best known algorithms have exponential running time of \mathcal{O}(n2^{n}) : these are due to Ryser [ 6 ] and Glynn [ 7 ] . A celebrated theoretical result was the sampling algorithm by Clifford and Clifford that can generate an n -photon Boson Sampling output with a computational cost that is, up to a factor of 2, equivalent to the computation of the permanent of a matrix of size n . Specifically, the running time of their algorithm is \mathcal{O}(n2^{n})+\mathcal{O}(mn^{2}) [ 1 ] . The prospect of performing an experimental demonstration of quantum advantage attracted a lot of experimental effort and further theoretical work, which recently lead to experiments claiming they have reached quantum advantage on photonic platforms [ 8 , 9 ] . It is known that one can design classical algorithms that exploit the presence of imperfections in the hardware, such as losses and distinguishability of photons, to run faster and potentially challenge the quantum advantage claims. For example, it was known that for integrated photonic circuits, composed of nearest-neighbour gates with transmission rates decaying exponentially with the depth of the circuit, circuits of depth D=\Omega(\log m) may be simulated as thermal noise in polynomial time, and that a noisy shallow circuit can be simulated in quasi-polynomial time using tensor networks [ 10 ] . The fact that simulating a shallow circuit, i.e. with depth D=\mathcal{O}(\log m) , requires quasi-polynomial time was expected to be a feature of the use of tensor network techniques, rather than a fundamental result. It was believed that one could find a polynomial time algorithm, for example using results about efficient computation of permanents of sparse matrices by Cifuentes & Parrilo [ 2 ] . Indeed, this combination was used by Oh et al. in [ 11 ] to prove some complexity results about the (non)-hardness of Boson Sampling circuits with a lattice structure. Furthermore, an efficient algorithm for shallow Gaussian Boson Sampling circuits, a variant of Boson Sampling using squeezed states instead of single photons, was proven by Qi et al. in [ 12 ] using similar ideas. In this work we revisit the inital conjecture in [ 10 ] and show how one can use the result of Cifuentes and Parillo [ 2 ] to design a polynomial time algorithm for Boson Sampling from shallow circuits, exploiting the fact that the computation of a permanent scales polynomially in the treewitdh of the graph corresponding to our photonic circuit of interest. A similar approach was given by Oh et al. [ 11 ] who gave the running time of \mathcal{O}(mn^{2}2^{\omega}\omega^{2}) . We present an algorithm that reproduces all the key advantages of the initial Clifford and Clifford algorithm in [ 1 ] adapted to the nearest-neighbors shallow circuit scenario. Our main technical contribution is the following:

Read the complete text