Approximating outcome probabilities of linear optical circuits
arXiv:2211.07184 · doi:10.1038/s41534-023-00791-9
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 -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.
arXiv comment27 pages, 2 figures, 2 tables
References in corpus (30)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum computational advantage using photons
- Continuous variable quantum information: Gaussian states and beyond
- Gaussian Boson Sampling
- Positive Wigner functions render classical simulation of quantum computation efficient
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Negative Quasi-Probability as a Resource for Quantum Computation
- Estimating outcome probabilities of quantum circuits using quasiprobabilities
- Convex resource theory of non-Gaussianity
- Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
- Gaussian Boson Sampling using threshold detectors
- Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
- What can quantum optics say about computational complexity theory?
- A Linear-Optical Proof that the Permanent is #P-Hard
- Regimes of classical simulability for noisy Gaussian boson sampling
- Quasiprobability representations of quantum mechanics with minimal negativity
- Negativity of quasiprobability distributions as a measure of nonclassicality
- From estimation of quantum probabilities to simulation of quantum circuits
- The Complexity of Bipartite Gaussian Boson Sampling
- Classical simulation of boson sampling based on graph structure
- Simulating complex networks in phase space: Gaussian boson sampling
- Efficient simulatability of continuous-variable circuits with large Wigner negativity
- Hafnians, perfect matchings and Gaussian matrices
- An efficient tree decomposition method for permanents and mixed discriminants
- A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
- Quantum software for linear photonic simulations
- Simulating and assessing boson sampling experiments with phase-space representations
- Quantum-inspired classical algorithm for molecular vibronic spectra
- Quantum-inspired permanent identities
- Simulating Quantum Circuits with Sparse Output Distributions