Boson sampling is fragile to loss
Authors: Youngrong Lim
Abstract
Boson sampling experiments aim to demonstrate quantum computational advantage with increasing numbers of interfering photons. A central question is whether their computational hardness survives under photon loss. We show that even an arbitrarily small nonzero uniform loss rate permits efficient classical sampling in the average case when the rate remains fixed as the system grows. We exploit how loss suppresses correlations involving many photons to approximate the full output distribution using low correlation orders. The resulting samplers run in time polynomial in system size and inverse total variation error, with the error averaged over Haar random interferometers. The results apply to Fock state boson sampling with single-photon states in distinct input modes and arbitrary additional vacuum inputs, and to Gaussian boson sampling with equal squeezing of bounded strength in every input mode. Classical sampling is efficient even when the mean detected photon number grows linearly with system size, showing that large photon counts alone do not ensure computational hardness.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
BosonSampling with Lost PhotonsS. Aaronson, D. Brod · 2015 · arXiv.org · preprint, not peer reviewed · cited 85 times · Not summarized yet
BosonSampling with Lost Photons studies how randomly losing source photons affects boson-sampling complexity and robustness.
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$ …
-
Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon LossByeong-Yoon Go, Hyunseok Jeong · 2026 · cited 1 time · Not summarized yet
Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss gives efficient classical sampling when a constant fraction of input photons survives.
Abstract
Understanding how photon loss changes the classical complexity of BosonSampling is central to assessing the robustness of near-term photonic quantum advantage. In this work, we present a polynomial-time classical simulation algorithm for lossy BosonSampling that applies whenever a constant fraction of the input photons survives. We consider the standard fixed-loss model, where $N$ input photons propagate through an $M$-mode interferometer and exactly $N-n$ photons are lost uniformly at random, leaving $n$ surviving photons at the output. For any constant surviving fraction $n/N\in(0,1)$, the algorithm samples from a distribution within total variation distance $\varepsilon$ of the fixed-loss…
-
Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root RegimeYoungrong Lim · 2026 · cited 2 times · Not summarized yet
Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root Regime simulates lossy Gaussian boson sampling by approximating detection rather than replacing the input with classical light.
Abstract
Photon loss makes Gaussian boson sampling easier to simulate classically. A standard approach replaces the lossy input by classical light, and it stays accurate while the mean number of surviving photons grows no faster than the square root of the number $N$ of squeezed inputs at fixed squeezing and accuracy. We prove that this scale is a limit of replacement by classical light. For explicit interferometers, no state with a nonnegative Glauber--Sudarshan $P$ representation, Gaussian or not and however correlated, keeps the error in the photon count distribution small beyond this scale. We then surpass this limit by approximating the detection instead of the input. The sampler evolves the sta…
-
Simulating boson sampling in lossy architecturesR. García-Patrón, J. Renema, V. Shchesnovich · 2017 · Quantum · cited 126 times · Not summarized yet
Simulating boson sampling in lossy architectures uses thermal-noise or tensor-network simulation for circuits with transmission that decays exponentially with depth.
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 re…
-
Polynomial-time classical simulation of boson and fermion sampling under thermal lossArmando Angrisani, Hela Mhiri · 2026 · Not summarized yet
Polynomial-time classical simulation of boson and fermion sampling under thermal loss proves efficient sampling for lossy Fock-state and Gaussian boson sampling.
Abstract
Sampling experiments are a leading approach to demonstrating quantum computational advantage, yet their robustness to experimental noise is not completely understood. We develop a common framework for classical simulation of boson and fermion sampling under thermal loss, including pure loss. For Fock-state boson sampling, Gaussian boson sampling with fixed uniform squeezing, and fermion sampling with magic inputs, we obtain polynomial-time sampling at inverse-polynomial total variation error, for any fixed nonzero overall loss rate, and with high probability over Haar-random interferometers. A milder flatness assumption on the ideal output distribution suffices for quasipolynomial-time simul…
-
Scalability and performance metrics for boson sampling devicesDong-Gil Im, Chung-Hyun Lee, Joonsuk Huh et al. · 2026 · Not summarized yet
Scalability and performance metrics for boson sampling devices examines how loss and other experimental constraints affect scalable quantum advantage.
Abstract
Linear-optical platforms provide a promising route to demonstrate quantum computational advantage, particularly through the boson sampling problem. While a boson sampling system should be large enough to show the quantum advantage, the size of the boson sampling problem is often restricted by experimental constraints. In particular, as a boson sampling system is scaled up, experimental constraints can limit its effective problem size to permit efficient classical simulation. In this paper, we investigate the theoretical scalability bounds for boson sampling systems under practical experimental conditions, including photon loss, mode mismatch, and input state error. We employ non-negativity c…
-
Sufficient conditions for hardness of lossy Gaussian boson samplingByeong-Yoon Go, Changhun Oh, Hyunseok Jeong · 2025 · cited 6 times · Not summarized yet
Sufficient conditions for hardness of lossy Gaussian boson sampling argues GBS remains intractable when at most a logarithmic fraction of photons is lost, unlike fixed-rate loss here.
Abstract
Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably subject to noise, the robustness of the classical intractability of GBS against noise remains largely unexplored. In this work, we establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss, which is a dominant source of imperfection in current implementations. We identify the loss threshold below which lossy GBS maintains the same complexity-theoretic level as ideal GBS, and show that this holds when at most a logarithmic fraction of photons is lost. We additionall…
-
Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable PhotonsByeong-Yoon Go, Changhun Oh, Hyunseok Jeong · 2025 · PRX Quantum · cited 11 times · Not summarized yet
Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable Photons identifies noise levels preserving hardness under partial distinguishability rather than photon loss.
Abstract
Boson sampling stands out as a promising approach toward experimental demonstration of quantum computational advantage. However, the presence of physical noise in near-term experiments hinders the realization of quantum computational advantage with boson sampling. Since physical noise in near-term boson-sampling devices is inevitable, precise characterization of the boundary of noise rates where the classical intractability of boson sampling is maintained is crucial for quantum computational advantage using near-term devices. In this work, we identify the level of partial-distinguishability noise that upholds the classical intractability of boson sampling. We find that boson sampling with on…
Prior work it builds on
-
Gaussian boson sampling with 1,024 squeezed states in 8,176 modesHua-Liang Liu, Hao-Ru Su, Yu-Hao Deng et al. · 2026 · Nature · cited 30 times · Not summarized yet
Gaussian boson sampling with 1,024 squeezed states in 8,176 modes reports a large-scale photonic processor and addresses photon-loss limits on scalability.
Abstract
The development of large-scale, high-fidelity quantum processors is a fundamental scientific challenge, essential for exploring the boundaries of classical computation and advancing towards fault-tolerant systems. Gaussian boson sampling not only serves as a prominent model for demonstrating quantum computational advantage1, 2–3 but can also generate bosonic error-correcting codes for fault-tolerant quantum computing4, 5–6. However, its scalability has been hindered by significant photon loss in increasingly large and complex encoding circuits. Here we show a programmable photonic quantum processor, Jiuzhang 4.0, which incorporates 1,024 high-efficiency squeezed states into a hybrid spatial–…
-
Classical simulation of photonic linear optics with lost particlesMichał Oszmaniec, D. Brod · 2018 · New Journal of Physics · cited 119 times · Not summarized yet
Classical simulation of photonic linear optics with lost particles studies efficient classical approximation of boson-sampling output statistics under particle loss.
Abstract
We explore the possibility of efficient classical simulation of linear optics experiments under the effect of particle losses. Specifically, we investigate the canonical boson sampling scenario in which an n-particle Fock input state propagates through a linear-optical network and is subsequently measured by particle-number detectors in the m output modes. We examine two models of losses. In the first model a fixed number of particles is lost. We prove that in this scenario the output statistics can be well approximated by an efficient classical simulation, provided that the number of photons that is left grows slower than n . In the second loss model, every time a photon passes through a be…
-
Regimes of Classical Simulability for Noisy Gaussian Boson Sampling.Hao-Yu Qi, D. Brod, N. Quesada et al. · 2019 · Physical Review Letters · cited 92 times · Not summarized yet
Regimes of Classical Simulability for Noisy Gaussian Boson Sampling gives a condition for efficient simulation of noisy GBS based on squeezing, transmission, and detector quality.
Abstract
As a promising candidate for exhibiting quantum computational supremacy, Gaussian boson sampling (GBS) is designed to exploit the ease of experimental preparation of Gaussian states. However, sufficiently large and inevitable experimental noise might render GBS classically simulable. In this work, we formalize this intuition by establishing a sufficient condition for approximate polynomial-time classical simulation of noisy GBS-in the form of an inequality between the input squeezing parameter, the overall transmission rate, and the quality of photon detectors. Our result serves as a nonclassicality test that must be passed by any quantum computational supremacy demonstration based on GBS. W…
-
Quantum computational advantage via high-dimensional Gaussian boson samplingA. Deshpande, Arthur Mehta, Trevor Vincent et al. · 2021 · Science Advances · cited 135 times · Not summarized yet
Quantum computational advantage via high-dimensional Gaussian boson sampling reports a fiber-optic quantum computer outperforming classical computers.
Abstract
A programmable quantum computer based on fiber optics outperforms classical computers with a high level of confidence.
-
Gaussian Boson samplingC. Hamilton, R. Kruse, L. Sansoni et al. · 2016 · Conference on Lasers and Electro-Optics · cited 542 times · Not summarized yet
Gaussian Boson sampling presents the squeezed-state protocol and Hafnian-based sampling framework used by the paper's Gaussian boson-sampling setting.
Abstract
We present the protocol for Gaussian Boson Sampling with single-mode squeezed states. We eliminate heralding and show that our proposal with the Hafnian matrix function can retain the higher photon number contributions at the input.
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 10 November 2026.