Efficient classical algorithms for linear optical circuits

• URL: http://arxiv.org/abs/2502.12882v1
• Date: Tue, 18 Feb 2025 14:13:24 GMT
• Title: Efficient classical algorithms for linear optical circuits
• Authors: Youngrong Lim, Changhun Oh,
• Abstract summary: We present efficient classical algorithms to approximate expectation values and probability amplitudes in linear optical circuits. This result suggests that certain applications of linear optical circuits relying on expectation value estimation, such as photonic variational algorithms, may face challenges in achieving quantum advantage.
• Score: 0.0
• License:
• Abstract: We present efficient classical algorithms to approximate expectation values and probability amplitudes in linear optical circuits. Specifically, our classical algorithm efficiently approximates the expectation values of observables in linear optical circuits for arbitrary product input states within an additive error under a mild condition. This result suggests that certain applications of linear optical circuits relying on expectation value estimation, such as photonic variational algorithms, may face challenges in achieving quantum advantage. In addition, the (marginal) output probabilities of boson sampling with arbitrary product input states can be efficiently approximated using our algorithm, implying that boson sampling can be efficiently simulated if its output probability distribution is polynomially sparse. Moreover, our method generalizes Gurvits's algorithm, originally designed to approximate the permanent, to also approximate the hafnian of complex symmetric matrices with an additive error. The algorithm also solves a molecular vibronic spectra problem for arbitrary product input states as precisely as boson samplers. Finally, our method extends to near-Clifford circuits, enabling the classical approximation of their expectation values of any observables and (marginal) output probabilities.

Related papers

• A Fourier analysis framework for approximate classical simulations of quantum circuits [0.0]
  I present a framework that applies harmonic analysis of groups to circuits with a structure encoded by group parameters. I also discuss generalisations to homogeneous spaces, qudit systems and a way to analyse random circuits via matrix coefficients of irreducible representations.
  arXiv  Detail & Related papers  (2024-10-17T17:59:34Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Differentiation of Linear Optical Circuits [0.0]
  This paper develops classical and quantum algorithms for evaluating the analytic gradients of linear optical circuits. We show how to compute the gradients of the expectation values of a special class of non-interacting'' observables arising in full-counting-statistics.
  arXiv  Detail & Related papers  (2024-01-15T22:43:22Z)
• Randomized semi-quantum matrix processing [0.0]
  We present a hybrid quantum-classical framework for simulating generic matrix functions. The method is based on randomization over the Chebyshev approximation of the target function. We prove advantages on average depths, including quadratic speed-ups on costly parameters.
  arXiv  Detail & Related papers  (2023-07-21T18:00:28Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Approximating outcome probabilities of linear optical circuits [0.0]
  We propose classical algorithms for approximating outcome probabilities of a linear optical circuit. Our scheme renders an efficient estimation of outcome probabilities with precision depending on the classicality of the circuit. Our study sheds light on the power of linear optics, providing plenty of quantum-inspired algorithms for problems in computational complexity.
  arXiv  Detail & Related papers  (2022-11-14T08:21:51Z)
• Learnability of the output distributions of local quantum circuits [53.17490581210575]
  We investigate, within two different oracle models, the learnability of quantum circuit Born machines. We first show a negative result, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable. We show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable.
  arXiv  Detail & Related papers  (2021-10-11T18:00:20Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone [2.5496329090462626]
  We examine classical simulability of sampling from the output photon-number distribution of linear-optical circuits. We show that the algorithms' error is exponentially small up to a depth less than quadratic in the distance between sources.
  arXiv  Detail & Related papers  (2021-02-19T18:33:31Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
  We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs.
  arXiv  Detail & Related papers  (2020-06-15T13:40:07Z)

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.