Distinguishing noisy boson sampling from classical simulations
arXiv:1905.11458 · doi:10.22331/q-2021-03-29-423
Abstract
Giving a convincing experimental evidence of the quantum supremacy over classical simulations is a challenging goal. Noise is considered to be the main problem in such a demonstration, hence it is urgent to understand the effect of noise. Recently found classical algorithms can efficiently approximate, to any small error, the output of boson sampling with finite-amplitude noise. In this work it is shown analytically and confirmed by numerical simulations that one can efficiently distinguish the output distribution of such a noisy boson sampling from the approximations accounting for low-order quantum multiboson interferences, what includes the mentioned classical algorithms. The number of samples required to tell apart the quantum and classical output distributions is strongly affected by the previously unexplored parameter: density of bosons, i.e., the ratio of total number of interfering bosons to number of input ports of interferometer. Such critical dependence is strikingly reminiscent of the quantum-to-classical transition in systems of identical particles, which sets in when the system size scales up while density of particles vanishes.
arXiv commentMarch 4, 2022 : In Appendix C.1 the derivation of the lower bound in Eq. (50) is simplified significantly. However, there is an additional error term in Eq. (13) of the main text
References in corpus (54)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Characterizing Quantum Supremacy in Near-Term Devices
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
- Tailoring Single and Multiphoton Probabilities of a Single Photon On-Demand Source
- Boson Sampling from Gaussian States
- Experimental Scattershot Boson Sampling
- On the experimental verification of quantum complexity in linear optics
- BosonSampling with single-photon Fock states from a bright solid-state source
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- No imminent quantum supremacy by boson sampling
- Scalable boson sampling with a single-photon device
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Scalable boson-sampling with time-bin encoding using a loop-based architecture
- 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
- Simulating boson sampling in lossy architectures
- Architectures for quantum simulation showing a quantum speedup
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- What can quantum optics say about computational complexity theory?
- A Linear-Optical Proof that the Permanent is #P-Hard
- Scalable Implementation of Boson Sampling with Trapped Ions
- A Statistical Benchmark for BosonSampling
- Error tolerance of the BosonSampling model for linear optics quantum computing
- Experimental statistical signature of many-body quantum interference
- Classical simulation of photonic linear optics with lost particles
- BosonSampling with Lost Photons
- Symbolic integration with respect to the Haar measure on the unitary group
- Experimental Gaussian Boson Sampling
- Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
- Universality of Generalized Bunching and Efficient Assessment of Boson Sampling
- Permanents in linear optical networks
- Microwave Boson Sampling
- Dynamical phase transitions in sampling complexity
- Pattern recognition techniques for Boson Sampling validation
- Boson-Sampling in the light of sample complexity
- Classical simulation of linear optics subject to nonuniform losses
- Gaussian Noise Sensitivity and BosonSampling
- 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
- Classical simulability of noisy boson sampling
- Collective phases of identical particles interfering on linear multiports
- A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
- Certification of Boson Sampling Devices with Coarse-Grained Measurements
- Boson Sampling is Robust to Small Errors in the Network Matrix
- Decoherence and Interferometric Sensitivity of BosonSampling in Superconducting Networks
- Distinguishability theory for time-resolved photodetection and boson sampling
Cited by in corpus (12)
- Computational advantage of quantum random sampling
- Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
- An atomic boson sampler
- Strong Simulation of Linear Optical Processes
- Distinguishability in quantum interference with the squeezed states
- Efficient validation of Boson Sampling from binned photon-number distributions
- BosonSampling.jl: A Julia package for quantum multi-photon interferometry
- Marginal probabilities in boson samplers with arbitrary input states
- Isoenergetic model for optical downconversion and error-specific limits of the parametric approximation
- Dynamical complexity of non-Gaussian many-body systems with dissipation
- Boosting Gaussian Boson Sampling using Optical Parametric Amplification Networks
- Sample space filling analysis for boson sampling validation