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.
27 pages, 2 figures, 2 tables
References in corpus (6)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum computational advantage using photons
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
- What can quantum optics say about computational complexity theory?
- Quantum-inspired permanent identities