Approximating outcome probabilities of linear optical circuits

• URL: http://arxiv.org/abs/2211.07184v2
• Date: Sun, 17 Dec 2023 11:57:30 GMT
• Title: Approximating outcome probabilities of linear optical circuits
• Authors: Youngrong Lim and Changhun Oh
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quasiprobability representation is an important tool for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using $s$-parameterized quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the norm-preserving property of a linear optical transformation. Consequently, our scheme renders an efficient estimation of outcome probabilities with precision depending on the classicality of the circuit. Surprisingly, when the classicality is high enough, we reach a polynomial-time estimation algorithm within a multiplicative error. Our results provide quantum-inspired algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian boson sampling using the approximating algorithm for any (marginal) outcome probability under the poly-sparse condition. Our study sheds light on the power of linear optics, providing plenty of quantum-inspired algorithms for problems in computational complexity.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Realization of the Finite Element Method [0.0]
  This paper presents a quantum algorithm for the solution of second-order linear elliptic partial differential equations discretized by $d$-linear finite elements. An essential step in the construction is a BPX preconditioner, which transforms the linear system into a sufficiently well-conditioned one. We provide a constructive proof demonstrating that, for any fixed dimension, our quantum algorithm can compute suitable functionals of the solution to a given tolerance.
  arXiv  Detail & Related papers  (2024-03-28T15:44:20Z)
• Complexity of Gaussian quantum optics with a limited number of non-linearities [4.532517021515834]
  We show that computing transition amplitudes of Gaussian processes with a single-layer of non-linearities is hard for classical computers. We show how an efficient algorithm to solve this problem could be used to efficiently approximate outcome probabilities of a Gaussian boson sampling experiment.
  arXiv  Detail & Related papers  (2023-10-09T18:00:04Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• 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)
• Simulating Quantum Computations with Tutte Polynomials [0.0]
  We establish a classical algorithm for exactly computing quantum probability amplitudes. Our algorithm is based on mapping output probability amplitudes of quantum circuits to evaluations of the Tutte of graphic matroids.
  arXiv  Detail & Related papers  (2021-01-01T11:11:44Z)
• Efficient phase-factor evaluation in quantum signal processing [1.3614427997190908]
  Quantum signal processing (QSP) is a powerful quantum algorithm to exactly implement matrixs on quantum computers. There is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits. We present here an optimization based method that can accurately compute the phase factors using standard double precision arithmetic operations.
  arXiv  Detail & Related papers  (2020-02-26T17:23:55Z)
• 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.