⚛️ quantum physics

Boson sampling is fragile to loss

This paper demonstrates that boson sampling loses its computational hardness and becomes efficiently simulable by classical algorithms even under arbitrarily small uniform photon loss, as loss suppresses high-order photon correlations allowing for accurate low-order approximations of the output distribution.

Original author: Youngrong Lim

Published 2026-11-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: Youngrong Lim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to prove that machines built from light can outperform the most powerful supercomputers, scientists have turned to a specific challenge called boson sampling. Imagine a complex maze of mirrors and beam splitters, where individual particles of light, known as photons, are sent in to interfere with one another. The goal is to predict where these photons will exit the maze. While a real machine can perform this task by simply running the experiment and recording the results, calculating the answer on a traditional computer is believed to be impossibly difficult as the number of photons increases. This difficulty is the foundation of a claim called quantum computational advantage: the idea that a quantum device can solve a problem that classical computers cannot touch. However, real-world experiments are never perfect. Light leaks, detectors miss particles, and the system loses photons along the way. For years, researchers have debated whether this inevitable loss destroys the quantum advantage or if the problem remains hard enough to prove a machine's superiority even when it is imperfect.

A new study by Youngrong Lim at Chungbuk National University provides a significant theoretical insight into this question, showing that the hope for a quantum advantage based solely on increasing the number of photons may be misplaced if the system suffers from a fixed rate of loss. The research demonstrates that if a constant fraction of photons is lost as the experiment grows larger, a classical computer can efficiently simulate the results in the average case, no matter how many photons are involved. The key insight is that losing photons acts as a filter that washes out the complex, high-level connections between many particles. When these deep correlations are suppressed, the remaining pattern becomes simple enough for a standard computer to recreate quickly. This finding suggests that simply adding more light to a system with a fixed efficiency will not be enough to guarantee a quantum advantage; the loss rate must drop to nearly zero as the system scales up for the problem to remain truly hard.

The study focuses on two common ways scientists set up these light experiments. In one version, single photons are sent into distinct paths, while in the other, the light is squeezed to create a different kind of quantum state. In both cases, the researchers modeled a scenario where the transmission rate—the percentage of photons that successfully reach the detectors—stays the same even as the number of input paths and photons grows. In real experiments, this is the most realistic situation, as every component, from the light source to the detector, has a fixed quality that does not improve just because the machine gets bigger. The author proved mathematically that under these conditions, a classical algorithm can generate samples that look statistically identical to the output of the quantum machine on average. The error between the classical simulation and the real quantum result can be made arbitrarily small, and the time it takes to do this grows only at a manageable, polynomial rate relative to the size of the system.

The mechanism behind this result relies on how loss affects the behavior of the photons. In a perfect system, the photons interfere with each other in a way that involves the entire group simultaneously, creating a pattern that is incredibly difficult to calculate. However, when photons are lost, the interference patterns that depend on large groups of particles become vanishingly rare. The researchers showed that the output distribution can be accurately approximated by looking only at the interactions between small groups of photons. Because the probability of needing to account for large groups drops off exponentially as the loss rate increases, a classical computer only needs to track these small, manageable interactions to reproduce the result. This means that even if the total number of detected photons grows linearly with the size of the machine, the underlying complexity does not scale up in a way that defeats classical computers.

This conclusion has significant implications for current and future experiments. Several large-scale photonic experiments have already claimed to demonstrate quantum advantage, often citing the sheer number of photons they detected as proof of their power. The new analysis suggests that these claims require careful re-evaluation. If the loss rate in these experiments remains fixed as they scale up, the results cannot guarantee a quantum computational advantage, meaning the observed advantage might not be as fundamental as hoped. The study does not rule out the possibility of quantum advantage entirely, but it narrows the open range for achieving it. To maintain a computational edge, the loss rate must decrease rapidly as the system grows, a condition that is far more difficult to achieve in practice than simply building a larger machine with the same components.

The research also clarifies the boundary between what is possible and what is not. While the author proved that a fixed loss rate allows for efficient classical simulation, they acknowledged that if the loss rate drops quickly enough—specifically, if the number of lost photons grows only logarithmically while the total number grows linearly—the problem remains hard. This leaves a very narrow window for quantum advantage: the system must be so efficient that the fraction of lost photons shrinks toward zero as the machine gets bigger. For now, the most favorable case for a quantum computer, where the transmission rate is high and constant, turns out to be the easiest for classical computers to mimic. The study serves as a crucial reality check, reminding the field that the path to proving quantum supremacy is not just about counting photons, but about controlling the delicate balance of loss and interference with extreme precision.

Technical Summary: Boson Sampling is Fragile to Loss

Problem Statement
Boson sampling is a leading candidate for demonstrating quantum computational advantage using non-universal photonic devices. The computational task involves sampling from the joint output distribution of indistinguishable photons interfering through a linear interferometer. While ideal boson sampling is believed to be classically intractable under plausible complexity assumptions, real-world experiments suffer from photon loss.

A critical open question is whether the computational hardness of boson sampling survives under a fixed, non-zero uniform loss rate. Previous results established hardness only when the number of lost photons is logarithmic in the system size, while efficient classical simulation was known only when the surviving fraction of photons tends to zero as the system grows. This left a broad, experimentally relevant regime unresolved: the case where the transmission rate $\eta$ is fixed (and thus the mean number of lost photons grows linearly with system size), yet the mean detected photon count also grows linearly.

Methodology
The paper addresses this gap by constructing efficient classical samplers for two standard families of input states under fixed uniform loss:

Lossy Fock State Boson Sampling: Single photons in distinct input modes.
Lossy Gaussian Boson Sampling: Squeezed vacuum states with equal squeezing in all input modes.

The core physical insight exploited is that uniform loss suppresses high-order correlations among photons. The author decomposes the output probability distribution into orthogonal correlation orders (polynomials of the photon counts). They demonstrate that for a fixed transmission $\eta < 1$ , the weight of correlations involving $h$ photons decays exponentially with $h$ (specifically as $\eta^h$ for Fock states).

The proposed algorithm proceeds in three main stages:

Correlation Truncation: The sampler approximates the full output distribution by retaining only correlation orders up to a cutoff $L$ . Due to the exponential decay of correlation weights, $L$ need only grow logarithmically with the inverse error $1/\epsilon$ and the number of detected photons to achieve a target total variation distance.
Efficient Evaluation: Evaluating the truncated distribution directly would be costly. The author employs a technique involving random grouping of modes and the use of determinant generating functions to estimate the overlap of the truncated state with output configurations. This avoids the quasipolynomial cost associated with summing over auxiliary configurations, reducing the evaluation cost to be polynomial in system size and $1/\epsilon$ .
Rejection Sampling: The estimated probabilities are used within a rejection sampling framework. To handle the potentially large variance in acceptance weights, the algorithm clips the weights at a level proportional to $1/\epsilon$ . This introduces a controlled bias that is accounted for in the total error budget, ensuring the final samples are drawn from a distribution close to the true lossy output.

Key Results
The paper proves two main theorems establishing the existence of efficient classical algorithms for the aforementioned problems:

Theorem 1 (Fock States): For any fixed transmission $\eta$ , there exists a classical randomized algorithm that samples from the lossy Fock state distribution with an average total variation distance $\epsilon$ over Haar-random interferometers. The running time per sample is polynomial in the number of modes $M$ , the number of photons $n$ , and $1/\epsilon$ .
Theorem 2 (Gaussian States): Similarly, for Gaussian boson sampling with equal squeezing $r$ in all modes and fixed transmission $\eta$ , an efficient classical sampler exists with running time polynomial in $M$ and $1/\epsilon$ .

Crucially, these results hold even when the mean number of detected photons grows linearly with the system size (e.g., $\eta n$ or $\eta M \sinh^2 r$ ). The error is measured as the total variation distance averaged over the Haar measure of interferometers.

Significance and Claims
The author claims that their results narrow the "hardness gap" significantly. They demonstrate that for Haar-random interferometers, a fixed loss rate—regardless of how small—prevents the establishment of an asymptotic quantum sampling advantage for these specific input families.

Resolution of the Fixed-Rate Regime: The paper resolves the previously open regime where loss is fixed. It shows that large photon counts alone do not ensure computational hardness if a fixed fraction of photons is lost.
Implications for Experiments: The results apply to current and future experiments (such as those using Haar-random unitaries) that operate at fixed transmission rates. The author argues that such experiments cannot guarantee quantum computational advantage solely by increasing the number of photons and modes, as the resulting distribution can be efficiently approximated classically.
Limitations and Scope: The author explicitly states that their results are average-case over Haar-random interferometers. They do not claim to spoof specific experimental devices with structured interferometers (e.g., time-domain loops) or to provide a practical "spoofing" implementation for a specific experiment, as the polynomial bounds may have large degrees or constants. Furthermore, they note that hardness may still survive if the loss rate vanishes faster than $O(\log n / n)$ , or if the system utilizes non-Haar random structures, different input states, or optical nonlinearities.

In conclusion, the paper establishes that for the standard models of boson sampling, the presence of any fixed uniform loss rate renders the problem classically tractable in the average case, challenging the assumption that scaling up photon numbers in lossy systems automatically leads to computational advantage.

More like this