Simulability of Imperfect Gaussian and Superposition Boson Sampling
arXiv:1911.10112 · doi:10.1103/PhysRevA.101.063840
Abstract
We study the hardness of classically simulating Gaussian boson sampling at nonzero photon distinguishability. We find that similar to regular boson sampling, distinguishability causes exponential attenuation of the many-photon interference terms in Gaussian boson sampling. Barring an open problem in the theory of matrix permanents, this leads to an efficient classical algorithm to simulate Gaussian boson sampling in the presence of distinguishability. We also study a new form of boson sampling based on photon number superposition states, for which we also show noise sensivity. The fact that such superposition boson sampling is not simulable with out method at zero distinguishability is the first evidence for the computational hardness of this problem.
References in corpus (39)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Near optimal single photon sources in the solid state
- Universal Linear Optics
- On-Demand Single Photons with High Extraction Efficiency and Near-Unity Indistinguishability from a Resonantly Driven Quantum Dot in a Micropillar
- Boson Sampling on a Photonic Chip
- Quantum Computational Supremacy
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- On-demand semiconductor single-photon source with near-unity indistinguishability
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- Gaussian Boson Sampling
- Towards optimal single-photon sources from polarized microcavities
- Boson Sampling from Gaussian States
- Experimental Scattershot Boson Sampling
- On the experimental verification of quantum complexity in linear optics
- No imminent quantum supremacy by boson sampling
- Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
- Toward Scalable Boson Sampling with Photon Loss
- Efficient algorithm for boson sampling with partially distinguishable photons
- Partial indistinguishability theory for multi-photon experiments in multiport devices
- Gaussian Boson Sampling for perfect matchings of arbitrary graphs
- Generation of non-classical light in a photon-number superposition
- Regimes of classical simulability for noisy Gaussian boson sampling
- Multiboson Correlation Interferometry with arbitrary single-photon pure states
- Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Boson sampling with Gaussian measurements
- Gaussian Noise Sensitivity and BosonSampling
- Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal Boson Sampling
- Noise in BosonSampling and the threshold of efficient classical simulatability
- Classically simulating near-term partially-distinguishable and lossy boson sampling
- Classical simulability of noisy boson sampling
- Hafnians, perfect matchings and Gaussian matrices
- Multi-Boson Correlation Sampling
- Symmetries and entanglement features of inner-mode resolved correlations of interfering nonidentical photons
- Partial distinguishability and photon counting probabilities in linear multiport devices
- Quantum De Moivre-Laplace theorem for noninteracting indistinguishable particles
Cited by in corpus (24)
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Computational advantage of quantum random sampling
- Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
- Resources for bosonic quantum computational advantage
- Teleportation of a genuine single-rail vacuum-one-photon qubit generated via a quantum dot source
- Certification of Gaussian Boson Sampling via graph theory
- Scattershot multiboson correlation sampling with random photonic inner-mode multiplexing
- Quantum supremacy of the many-body fluctuations in the occupations of the excited particle states in a Bose-Einstein-condensed gas
- Sample-efficient benchmarking of multi-photon interference on a boson sampler in the sparse regime
- Gaussian boson sampling with partial distinguishability
- Classical simulability of constant-depth linear-optical circuits with noise
- Quantum interferences and gates with emitter-based coherent photon sources
- Towards Photon-Number-Encoded High-dimensional Entanglement from a Sequentially Excited Quantum Three-Level System
- Quantum memristor with vacuum--one-photon qubits
- Efficient approximation of experimental Gaussian boson sampling
- Gaussian boson sampling at finite temperature
- Boson sampling with random numbers of photons
- Validation of a noisy Gaussian boson sampler via graph theory
- On computational complexity and average-case hardness of shallow-depth boson sampling
- Quantum computational advantage of noisy boson sampling with partially distinguishable photons
- Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
- Optical Quantum Computing
- Resourcefulness of non-classical continuous-variable quantum gates
- Realistic photon-number resolution in Gaussian boson sampling