What can quantum optics say about computational complexity theory?
arXiv:1408.3712 · doi:10.1103/PhysRevLett.114.060501
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 (11)
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Boson Sampling from Gaussian States
- Stringent and efficient assessment of Boson-Sampling devices
- Direct characterization of linear-optical networks
- A Linear-Optical Proof that the Permanent is #P-Hard
- Mixing nonclassical pure states in a linear-optical network almost always generates modal entanglement
- Spontaneous parametric down-conversion photon sources are scalable in the asymptotic limit for boson-sampling
Cited by in corpus (59)
- Quantum computational advantage using photons
- Quantum Chemistry in the Age of Quantum Computing
- Gaussian Boson Sampling
- A detailed study of Gaussian Boson Sampling
- Computational advantage of quantum random sampling
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
- Simulating boson sampling in lossy architectures
- Quantum simulation of molecular spectroscopy in trapped-ion device
- Experimental Gaussian Boson Sampling
- Vibronic Boson Sampling: Generalized Gaussian Boson Sampling for Molecular Vibronic Spectra at Finite Temperature
- Quantum Experiments and Graphs II: Quantum Interference, Computation and State Generation
- Boson sampling with Gaussian measurements
- Negativity of quasiprobability distributions as a measure of nonclassicality
- Point Processes with Gaussian Boson Sampling
- Quantum computation and simulation with vibrational modes of trapped ions
- Approximating Vibronic Spectroscopy with Imperfect Quantum Optics
- Quantum Experiments and Hypergraphs: Multi-Photon Sources for Quantum Interference, Quantum Computation and Quantum Entanglement
- Quantum Correlations in Nonlocal BosonSampling
- Generalized concurrence in boson sampling
- Exact Boson Sampling using Gaussian continuous variable measurements
- Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
- A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
- Information processing at the speed of light
- Decision and function problems based on boson sampling
- Implementing quantum algorithms on temporal photonic cluster states
- Distinguishing noisy boson sampling from classical simulations
- Classical models may be a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model
- Boson sampling with non-identical single photons
- Error mitigation on a near-term quantum photonic device
- Quantum-inspired permanent identities
- Verifying single-mode nonclassicality beyond negativity in phase space
- Sufficient condition for universal quantum computation using bosonic circuits
- Certification of Gaussian Boson Sampling via graph theory
- Multimode Bogoliubov transformation and Husimi's Q-function
- 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
- Majorization and the time complexity of linear optical networks
- Quantum Emulation of Molecular Force Fields: A Blueprint for a Superconducting Architecture
- Photon-number moments and cumulants of Gaussian states
- In situ characterization of linear-optical networks in randomized boson sampling
- Experimental linear optical computing of the matrix permanent
- Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
- Partial Distinguishability as a Coherence Resource in Boson Sampling
- Approximating outcome probabilities of linear optical circuits
- Cumulant expansion for fast estimate of non-Condon effects in vibronic transition profiles
- Entanglement in the full state vector of boson sampling
- Gaussian boson sampling at finite temperature
- Transition of Anticoncentration in Gaussian Boson Sampling
- The Second Moment of Hafnians in Gaussian Boson Sampling
- Quantum Computing for Molecular Vibronic Spectra and Gaussian Boson Sampling
- A duality at the heart of Gaussian boson sampling
- Quantum estimation bound of Gaussian matrix permanent
- Validation of a noisy Gaussian boson sampler via graph theory
- Absorption to Fluctuating Bunching States in Non-Unitary Boson Dynamics
- Noise-reduction of multimode Gaussian Boson Sampling circuits via Unitary Averaging
- Photonic Simulation of Localization Phenomena Using Boson Sampling
- Analog quantum simulation of non-Condon effects in molecular spectroscopy
- Optical Quantum Computing