What can quantum optics say about computational complexity theory?

Abstract

Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain results that are of interest from both quantum theory and the computational complexity theory point of view. We derive a general formula for calculating the output probabilities, and by considering input thermal states, we show that the output probabilities are proportional to permanents of positive-semidefinite Hermitian matrices. It is believed that approximating permanents of complex matrices in general is a #P-hard problem. However, we show that these permanents can be approximated with an algorithm in BPP^NP complexity class, as there exists an efficient classical algorithm for sampling from the output probability distribution. We further consider input squeezed-vacuum states and discuss the complexity of sampling from the probability distribution at the output.

5 pages, 1 figure

References in corpus (1)

• Photonic Boson Sampling in a Tunable Circuit

Cited by in corpus (27)

• Quantum computational advantage using photons
• Computational advantage of quantum random sampling
• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• Experimental Gaussian Boson Sampling
• Exact Boson Sampling using Gaussian continuous variable measurements
• Information processing at the speed of light
• Classical models may be a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model
• Quantum-inspired permanent identities
• Certification of Gaussian Boson Sampling via graph theory
• Sufficient condition for universal quantum computation using bosonic circuits
• Phase-space negativity as a computational resource for quantum kernel methods
• Simulating the Photon Statistics of Multimode Gaussian States by Automatic Differentiation of Generating Functions
• Photon-number moments and cumulants of Gaussian states
• Experimental linear optical computing of the matrix permanent
• Approximating outcome probabilities of linear optical circuits
• Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
• The Second Moment of Hafnians in Gaussian Boson Sampling
• Gaussian boson sampling at finite temperature
• Transition of Anticoncentration in Gaussian Boson Sampling
• Entanglement in the full state vector of boson sampling
• Validation of a noisy Gaussian boson sampler via graph theory
• A duality at the heart of Gaussian boson sampling
• Quantum estimation bound of Gaussian matrix permanent
• Absorption to Fluctuating Bunching States in Non-Unitary Boson Dynamics
• Photonic Simulation of Localization Phenomena Using Boson Sampling
• Noise-reduction of multimode Gaussian Boson Sampling circuits via Unitary Averaging
• Optical Quantum Computing