Classical simulation of linear optics subject to nonuniform losses

Abstract

We present a comprehensive study of the impact of non-uniform, i.e.\ path-dependent, photonic losses on the computational complexity of linear-optical processes. Our main result states that, if each beam splitter in a network induces some loss probability, non-uniform network designs cannot circumvent the efficient classical simulations based on losses. To achieve our result we obtain new intermediate results that can be of independent interest. First, we show that, for any network of lossy beam-splitters, it is possible to extract a layer of non-uniform losses that depends on the network geometry. We prove that, for every input mode of the network it is possible to commute $s_i$ layers of losses to the input, where $s_i$ is the length of the shortest path connecting the $i$th input to any output. We then extend a recent classical simulation algorithm due to P. Clifford and R. Clifford to allow for arbitrary $n$-photon input Fock states (i.e. to include collision states). Consequently, we identify two types of input states where boson sampling becomes classically simulable: (A) when $n$ input photons occupy a constant number of input modes; (B) when all but $O(\log n)$ photons are concentrated on a single input mode, while an additional $O(\log n)$ modes contain one photon each.

arXiv comment14 pages, 5 figures, v4: final version accepted in Quantum, acknowledgements slightly modified

References in corpus (37)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Characterizing Quantum Supremacy in Near-Term Devices
• Universal Linear Optics
• Boson Sampling on a Photonic Chip
• Quantum Computational Supremacy
• Multidimensional quantum entanglement with large-scale integrated optics
• 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 $10^{14}$ state spaces
• Gaussian Boson Sampling
• Efficient experimental validation of photonic boson sampling against the uniform distribution
• 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
• No imminent quantum supremacy by boson sampling
• Scalable boson sampling with a single-photon device
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Toward Scalable Boson Sampling with Photon Loss
• Efficient algorithm for boson sampling with partially distinguishable photons
• Simulating boson sampling in lossy architectures
• Regimes of classical simulability for noisy Gaussian boson sampling
• Classical simulation of photonic linear optics with lost particles
• BosonSampling with Lost Photons
• How many qubits are needed for quantum computational supremacy?
• Quantum optical realization of arbitrary linear transformations allowing for loss and gain
• A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
• Generation of Universal Linear Optics by Any Beamsplitter
• Gaussian Noise Sensitivity and BosonSampling
• Universality of single qudit gates
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Classical simulability of noisy boson sampling
• Generalized concurrence in boson sampling
• Quantum simulation of partially distinguishable boson sampling
• Boson Sampling is Robust to Small Errors in the Network Matrix
• Classical simulation of boson sampling with sparse output
• Analysis of circuit imperfections in BosonSampling

Cited by in corpus (25)

• Quantum circuits with many photons on a programmable nanophotonic chip
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Beyond photon pairs: Nonlinear quantum photonics in the high-gain regime
• Classical simulation of lossy boson sampling using matrix product operators
• High photon-loss threshold quantum computing using GHZ-state measurements
• Two strategies for modeling nonlinear optics in lossy integrated photonic structures
• Distinguishing noisy boson sampling from classical simulations
• Mitigating errors by quantum verification and post-selection
• Certification of Gaussian Boson Sampling via graph theory
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Simulating photonic devices with noisy optical elements
• Efficient validation of Boson Sampling from binned photon-number distributions
• Quantum error cancellation in photonic systems -- undoing photon losses
• Piquasso: A Photonic Quantum Computer Simulation Software Platform
• Classical simulability of constant-depth linear-optical circuits with noise
• BosonSampling.jl: A Julia package for quantum multi-photon interferometry
• High performance Boson Sampling simulation via data-flow engines
• 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
• Realistic photon-number resolution in Gaussian boson sampling
• Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
• Optical Quantum Computing
• Mitigating quantum operation infidelity through engineering the distribution of photon losses
• Building a fusion-based quantum computer using teleported gates