Simulating boson sampling in lossy architectures
arXiv:1712.10037 · doi:10.22331/q-2019-08-05-169
Abstract
Photon losses are among the strongest imperfections affecting multi-photon interference. Despite their importance, little is known about their effect on boson sampling experiments. In this work we show that using classical computers, one can efficiently simulate multi-photon interference in all architectures that suffer from an exponential decay of the transmission with the depth of the circuit, such as integrated photonic circuits or optical fibers. We prove that either the depth of the circuit is large enough that it can be simulated by thermal noise with an algorithm running in polynomial time, or it is shallow enough that a tensor network simulation runs in quasi-polynomial time. This result suggests that in order to implement a quantum advantage experiment with single-photons and linear optics new experimental platforms may be needed.
References in corpus (11)
- Photonic Boson Sampling in a Tunable Circuit
- DMRG and periodic boundary conditions: a quantum information perspective
- High-speed linear optics quantum computing using active feed-forward
- Toward Scalable Boson Sampling with Photon Loss
- What can quantum optics say about computational complexity theory?
- Classical simulation of photonic linear optics with lost particles
- On the simulation of quantum circuits
- Tensor network states in time-bin quantum optics
- Classical simulability of noisy boson sampling
- Exact Boson Sampling using Gaussian continuous variable measurements
- Efficient Computation of the Permanent of Block Factorizable Matrices
Cited by in corpus (71)
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Scalable integrated single-photon source
- Computational advantage of quantum random sampling
- Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
- Efficient classical simulation of noisy random quantum circuits in one dimension
- Encoding an oscillator into many oscillators
- The Boundary for Quantum Advantage in Gaussian Boson Sampling
- Regimes of classical simulability for noisy Gaussian boson sampling
- Beyond photon pairs: Nonlinear quantum photonics in the high-gain regime
- Resources for bosonic quantum computational advantage
- Scalable and Programmable Phononic Network with Trapped Ions
- Classical algorithm for simulating experimental Gaussian boson sampling
- Reconfigurable continuously-coupled 3D photonic circuit for Boson Sampling experiments
- Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
- Classical simulation of lossy boson sampling using matrix product operators
- The Complexity of Bipartite Gaussian Boson Sampling
- Classical simulation of boson sampling based on graph structure
- Classical simulation of linear optics subject to nonuniform losses
- Noise and the frontier of quantum supremacy
- An atomic boson sampler
- Quantum machine learning with Adaptive Boson Sampling via post-selection
- Efficient verification of Boson Sampling
- Classically simulating near-term partially-distinguishable and lossy boson sampling
- Quantum machine learning with adaptive linear optics
- Two strategies for modeling nonlinear optics in lossy integrated photonic structures
- Spoofing cross entropy measure in boson sampling
- Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
- Simulating lossy Gaussian boson sampling with matrix product operators
- Non-linear Boson Sampling
- Complexity phase diagram for interacting and long-range bosonic Hamiltonians
- Distinguishing noisy boson sampling from classical simulations
- Multiphoton Tomography with Linear Optics and Photon Counting
- Experimental demonstration of Gaussian boson sampling with displacement
- Error mitigation on a near-term quantum photonic device
- Simulating the Dynamics of Single Photons in BosonSampling Devices with Matrix Product States
- Threshold detection statistics of bosonic states
- Optimizing spontaneous parametric down-conversion sources for boson sampling
- Quantum Advantage for Shared Randomness Generation
- Certification of Gaussian Boson Sampling via graph theory
- Noise thresholds for classical simulability of non-linear Boson sampling
- Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
- Efficient validation of Boson Sampling from binned photon-number distributions
- Piquasso: A Photonic Quantum Computer Simulation Software Platform
- Distinguishability theory for time-resolved photodetection and boson sampling
- Linear multiport photonic interferometers: loss analysis of temporally-encoded architectures
- BosonSampling.jl: A Julia package for quantum multi-photon interferometry
- Classical simulability of constant-depth linear-optical circuits with noise
- Comparison of Controlled-Z operation and beam-splitter transformation for generation of squeezed Fock states by measurement
- Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
- Marginal probabilities in boson samplers with arbitrary input states
- Classical simulation of bosonic linear-optical random circuits beyond linear light cone
- High performance Boson Sampling simulation via data-flow engines
- Demonstration of quantum projective simulation on a single-photon-based quantum computer
- Complex structure and characterization of multi-photon split states in integrated circuits
- Validation of a noisy Gaussian boson sampler via graph theory
- Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
- Mitigating photon loss in linear optical quantum circuits
- Quantum computational advantage of noisy boson sampling with partially distinguishable photons
- On computational complexity and average-case hardness of shallow-depth boson sampling
- Sampling and the complexity of nature
- Boosting Gaussian Boson Sampling using Optical Parametric Amplification Networks
- Physical Unclonable Functions with Boson Sampling
- Classical modelling of a bosonic sampler with photon collisions
- Time-domain Hong-Ou-Mandel interference of quasi-thermal fields and its application in linear optical circuit characterization
- Resourcefulness of non-classical continuous-variable quantum gates
- Boundaries for quantum advantage with single photons and loop-based time-bin interferometers
- Optical Quantum Computing
- Classical algorithms for measurement-adaptive Gaussian circuits
- Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
- Realistic photon-number resolution in Gaussian boson sampling
- Quantum advantage for single-photon state characterization