Fast and memory efficient strong simulation of noisy adaptive linear optical circuits

• URL: http://arxiv.org/abs/2503.05699v1
• Date: Fri, 07 Mar 2025 18:59:16 GMT
• Title: Fast and memory efficient strong simulation of noisy adaptive linear optical circuits
• Authors: Timothée Goubault de Brugière, Nicolas Heurtel,
• Abstract summary: We propose an algorithm that models the output amplitudes as partial derivatives of a multivariate.<n>In terms of memory, storing one path from the root to the leaves is sufficient to iterate over all amplitudes and requires only $2n$ elements, as opposed to $binomn+m-1n$ for the fastest state of the art method.<n>This approach effectively balances the time-memory trade-off while extending to both noisy and feedforward scenarios with negligible cost.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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$ elements, as opposed to $\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.

Related papers

• Augmenting Simulated Noisy Quantum Data Collection by Orders of Magnitude Using Pre-Trajectory Sampling with Batched Execution [47.60253809426628]
  We present the Pre-Trajectory Sampling technique, increasing efficiency and utility of trajectory simulations by tailoring error types. We generate massive datasets of one trillion and one million shots, respectively.
  arXiv  Detail & Related papers  (2025-04-22T22:36:18Z)
• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
  Large Language Models (LLMs) are indispensable in today's applications, but their inference procedure demands significant computational resources. This paper formulates LLM inference optimization as a multi-stage online scheduling problem. We develop a fluid dynamics approximation to provide a tractable benchmark that guides algorithm design.
  arXiv  Detail & Related papers  (2025-04-15T16:00:21Z)
• Sublinear scaling in non-Markovian open quantum systems simulations [0.0]
  We introduce a numerically exact algorithm to calculate process tensors. Our approach requires only $mathcalO(nlog n)$ singular value decompositions for environments with infinite memory.
  arXiv  Detail & Related papers  (2023-04-11T15:40:33Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Strong Simulation of Linear Optical Processes [2.3131309703965135]
  Given $n$ photons at the input of an $m$-mode interferometer, our algorithm computes the probabilities of all possible output states. It outperforms the permanent-based method by an exponential factor.
  arXiv  Detail & Related papers  (2022-06-21T17:27:17Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Algorithmic Solution for Systems of Linear Equations, in $\mathcal{O}(mn)$ time [0.0]
  We present a novel algorithm attaining excessively fast, the sought solution of linear systems of equations. The execution time is very short compared with state-of-the-art methods. The paper also comprises a theoretical proof for the algorithmic convergence.
  arXiv  Detail & Related papers  (2021-04-26T13:40:31Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators [13.151348595345604]
  We show that the method based on Matrix Product States (MPS) fails to approximate the noisy output quantum states for any of the noise models considered. We propose a more effective tensor updates scheme with optimal truncations for both the inner and the bond dimensions.
  arXiv  Detail & Related papers  (2020-04-06T03:26:59Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning. We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
  arXiv  Detail & Related papers  (2020-02-10T10:11:31Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.