Fast and memory efficient strong simulation of noisy adaptive linear optical circuits
Timothée Goubault de Brugière, Nicolas Heurtel · 2025
Read Fast and memory efficient strong simulation of noisy adaptive linear optical circuits by Timothée Goubault de Brugière, Nicolas Heurtel (2025) 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-2503-05699.txt.
Introduction
Timothée Goubault de Brugière and Nicolas Heurtel write a 2025 paper on simulating light-based quantum circuits. Exact forecasts of what such a circuit will output are costly. Known methods are either fast but hungry for memory, or lean but slow, and real devices also add noise and mid-run feedback.
The new algorithm treats output strengths as parts of one large polynomial and works through its derivative lattice. Each step reuses prior work, and only one path through the lattice must be stored at a time. Memory needs fall far below the fastest known method. The same approach handles noise and feedback at little extra cost. Tests reach systems that were out of reach before.
Catalog record
| CREATOR | Timothée Goubault de Brugière, Nicolas Heurtel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-05699
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast and memory efficient strong simulation of noisy adaptive linear optical circuits Timothée Goubault de Brugière, Nicolas Heurtel Abstract Exactly computing the full output distribution of linear optical circuits remains a challenge, as existing methods are either time-efficient but memory-intensive or memory-efficient but slow. Moreover, any realistic simulation must account for noise, and any viable quantum computing scheme based on linear optics requires feedforward. In this paper, we propose an algorithm that models the output amplitudes as partial derivatives of a multivariate polynomial. The algorithm explores the lattice of all intermediate partial derivatives, where each derivative is used to compute more efficiently ones with higher degree. In terms of memory, storing one path from the root to the leaves is sufficient to iterate over all amplitudes and requires only 2 n 2^{n} elements, as opposed to ( n + m − 1 n ) \binom{n+m-1}{n} for the fastest state of the art method. This approach effectively balances the time-memory trade-off while extending to both noisy and feedforward scenarios with negligible cost. To the best of our knowledge, this is the first approach in the literature to meet all these requirements. We demonstrate how this method enables the simulation of systems that were previously out of reach, while providing a concrete implementation and complexity analysis. 1 Introduction Linear optics stands out as a natural and viable platform for carrying quantum information, enabling applications in secure communication [ 6 , 7 ] and quantum networks [ 22 , 41 ] . More importantly, linear optics with feedforward — the adaptive process of using outcomes from one stage to dynamically adjust the operations performed at a later stage in the circuit — has been shown to be sufficient for implementing any quantum algorithm [ 23 ] . The versatility and computational power of linear optics have led to extensive studies both in the context of passive implementations [ 1 , 32 , 27 ] and adaptive approaches for quantum applications [ 10 , 20 ] and scalable quantum computing schemes [ 43 , 28 , 9 , 5 , 15 , 3 ] . To effectively study and characterize optical processes, it is crucial to have efficient algorithms for computing output probabilities. A well-studied case is the computation of a single probability [ 35 , 1 ] , which can be computed with the permanent of a matrix with repeated rows [ 38 , 2 , 39 ] , where efficient and optimized implementations exist [ 17 , 18 , 36 ] . Though in many cases, the focus isn’t limited to a single probability but extends to multiple probabilities or even the entire output distribution. For an input of n photons over m modes, this distribution consists of \binom{n+m-1}{n} possible output states. Computing the full distribution by calculating the permanent independently for each output would be too time-consuming, making it essential to optimize computation time. Several methods have been proposed to efficiently and exactly compute multiple probabilities [ 19 ] by storing intermediary results, therefore gaining time by using an intense use of memory. While the proposed methods offer a significant time advantage, the bottleneck now becomes the memory, making the computation quickly intractable on any device with reasonable memory requirements. A more memory-efficient approach would be to iterate through all output states without storing large intermediate results. Moreover, linear optics proves especially useful in scenarios involving feedforward. However, to the best of the authors’ knowledge, no efficient algorithm has yet been proposed for strongly simulating linear optical circuits with feedforward. Coupled with the realistic requirement of handling noise [ 13 , 30 , 37 ] in physical experiments, we therefore seek an approach that optimally balances the time-space trade-off and is particularly suited for both feedforward and noisy simulations. In this paper, we introduce LO-SLAP (Linear Optical Simulation through LAttice of Polynomials), a memory-efficient algorithm that can iterate over the output amplitudes and be extended to feedfoward and noisy simulations with negligible cost. The iteration is achieved by exploiting the fact that amplitudes can also be viewed as nth-order partial derivatives of a multivariate polynomial. By storing information about a lower-order partial derivative, it is possible to calculate all child derivatives more efficiently. The algorithm uses 2^{n} in memory, compared with \binom{n+m-1}{n} for SLOS method of [ 19 ] , such that we removed the dependency in the number of modes m . Even though the memory requirement is still exponential in the number of photons, we can theoretically go as high as 30 photons on a laptop. We provide a theoretical analysis of the complexity of LO-SLAP and show that we actually increase significantly the problem sizes one can strongly simulate with reasonable computation power. We explicit how LO-SLAP extends to the noisy and feedforward case: 1. All intermediate coefficients that are calculated during the algorithm are actually output amplitudes of the same experiment but with input states with a lower photon count. We will show that LO-SLAP naturally computes all possible outputs of any input state with n photons or less. Therefore, at no extra cost , LO-SLAP can be used for strong simulation dealing with loss as well. We also show how to incorporate other sources of noise such as distinguishability. 2. Our method also handles feedforward with the only extra computation of computing the updated matrix of the experiment after a measurement — cost that any algorithm simulating feedforward has to compute. To the best of our knowledge, this is the first time that a strong simulation method handling feedforward has been proposed for linear optics. We compare it against an extended version of SLOS [ 19 ] and demonstrate a theoretical as well as a practical advantage. The plan of the article is the following. First in Section 2 we present the polynomial formalism of linear optical experiments, with a review of the existing methods to perform classical simulations. Then we present LO-SLAP in Section 3 , we explicit the data structure, how we update it and how we iterate over the output amplitudes. In Section 4 we present our two extensions: feedforward and noisy simulation. We conclude in Section 5 . 2 Background and state of the art 2.1 Formalism of linear optics Fock states. We consider a system of n photons and m modes. The canonical states of the system are the so-called Fock states \ket{s}=\ket{s_1, s_2, \hdots, s_m},\;\;\;\;\;|s|=\sum_{i=1}^{m}s_{i}=n which give the possible distributions of the photons into the different modes (we read s_{i} photons in the i-th mode). There are \binom{n+m-1}{n} ways to divide n photons into m modes (see the “stars and bars” theorem, for instance in [ 12 ] ). We note \Phi_{m,n} the set of all \binom{n+m-1}{n} Fock states. We also naturally associate a Fock state \ket{s} with an array r_{s}\in[m]^{n} that gives the output mode of each photon. For instance, with \ket{s}=\ket{0,2,1,0,1} , we can have r_{s}=[2,2,3,5] or any other permutation of r_{s} . The state \ket{\psi} of a linear optical system is a complex normalized linear combination of all possible Fock states of \Phi_{m,n} : \ket{\psi}=\sum_{s\in\Phi_{m,n}}\alpha_{s}\ket{s},\;\;\;\sum_{s}|\alpha_{s}|^{2}=1 where each |\alpha_{s}|^{2} gives the probability of measuring s if we measure the state \ket{\psi} . The coefficients \alpha_{s} are called the