BosonSampling with Lost Photons

Abstract

BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here we investigate the complexity of BosonSampling under photon losses---more specifically, the case where an unknown subset of the photons are randomly lost at the sources. We show that, if $k$ out of $n$ photons are lost, then we cannot sample classically from a distribution that is $1/n^{\Theta (k)}$-close (in total variation distance) to the ideal distribution, unless a ${\text{BPP}}^{\text{NP}}$ machine can estimate the permanents of Gaussian matrices in $n^{O(k)}$ time. In particular, if $k$ is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case.

12 pages. v2: extended concluding section

References in corpus (3)

• Photonic Boson Sampling in a Tunable Circuit
• Experimental Scattershot Boson Sampling
• Gaussian Noise Sensitivity and BosonSampling

Cited by in corpus (54)

• Photonic quantum information processing: a review
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Gaussian Boson Sampling
• On-demand semiconductor source of entangled photons which simultaneously has high fidelity, efficiency, and indistinguishability
• Scalable integrated single-photon source
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• No imminent quantum supremacy by boson sampling
• Computational advantage of quantum random sampling
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Toward Scalable Boson Sampling with Photon Loss
• Simulating boson sampling in lossy architectures
• Regimes of classical simulability for noisy Gaussian boson sampling
• Classical simulation of photonic linear optics with lost particles
• Experimental Gaussian Boson Sampling
• Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing
• Boson sampling with Gaussian measurements
• Classical simulation of lossy boson sampling using matrix product operators
• Dynamical phase transitions in sampling complexity
• Pattern recognition techniques for Boson Sampling validation
• The Complexity of Bipartite Gaussian Boson Sampling
• Classical simulation of boson sampling based on graph structure
• Experimental generalized quantum suppression law in Sylvester interferometers
• Classical simulation of linear optics subject to nonuniform losses
• Benchmarking integrated photonic architectures
• Quantum machine learning with Adaptive Boson Sampling via post-selection
• Noise in BosonSampling and the threshold of efficient classical simulatability
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Towards Quantum Supremacy with Lossy Scattershot Boson Sampling
• Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
• Quantum simulation of partially distinguishable boson sampling
• Information processing at the speed of light
• Non-linear Boson Sampling
• Distinguishing noisy boson sampling from classical simulations
• Simulating the Dynamics of Single Photons in BosonSampling Devices with Matrix Product States
• A robust W-state encoding for linear quantum optics
• Measurement-Based Linear Optics
• The scaling of boson sampling experiments
• Exact sampling hardness of Ising spin models
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits
• Noise thresholds for classical simulability of non-linear Boson sampling
• Simulating photonic devices with noisy optical elements
• Efficient validation of Boson Sampling from binned photon-number distributions
• Hardware requirements for realizing a quantum advantage with deterministic single-photon sources
• Error-mitigated photonic quantum circuit Born machine
• Correlations for subsets of particles in symmetric states: what photons are doing within a beam of light when the rest are ignored
• Distinguishability theory for time-resolved photodetection and boson sampling
• Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
• Boson sampling with ultracold atoms in a programmable optical lattice
• Advancing Quantum Networking: Some Tools and Protocols for Ideal and Noisy Photonic Systems
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• Interferometrically estimating a quadratic form for any immanant of a matrix and its permutations
• Mitigating photon loss in linear optical quantum circuits
• Boosting Gaussian Boson Sampling using Optical Parametric Amplification Networks
• Classical modelling of a bosonic sampler with photon collisions