⚛️ quantum physics

Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root Regime

This paper establishes that replacing lossy Gaussian boson sampling inputs with classical light is fundamentally limited to a square-root scaling of surviving photons, but proposes a novel detection-based approximation method that extends the efficient classical simulation regime to $N^{2/3}$ (or $N^{3/4}$ under specific conditions) by evolving the state exactly between detections and approximating the post-detection state.

Original authors: Youngrong Lim

Published 2026-10-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: 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 authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to build machines that solve problems beyond the reach of today's computers, scientists are turning to light. Specifically, they are using a technique called Gaussian boson sampling, which involves sending squeezed light—a special kind of laser beam where the uncertainty of the light wave is squeezed down in one direction—through a complex maze of mirrors and beam splitters. The goal is to measure how many photons, or particles of light, arrive at the detectors at the end. Because the light waves interfere with one another in incredibly complex ways, predicting the outcome of this experiment is thought to be a task that only a quantum computer could handle efficiently. If a classical computer, like the one on your desk, cannot keep up, it proves that the quantum machine has achieved a genuine advantage. However, real-world experiments are never perfect. The most common flaw is that photons get lost along the way, absorbed by the glass or scattered out of the system. This loss is a double-edged sword: while it makes the experiment harder to run, it also makes the results easier for a classical computer to fake. For years, researchers believed that as long as the number of surviving photons stayed below a certain threshold—specifically, growing no faster than the square root of the total number of input light beams—a classical computer could simply replace the complex quantum light with ordinary, classical light and simulate the results with high accuracy.

A new study challenges the idea that this square-root limit is an unbreakable wall for classical simulation. The researchers, working with a specific type of optical setup, demonstrated that the old method of replacing the input light with classical light hits a hard ceiling. They proved mathematically that no matter how cleverly one tries to model the lost light using classical statistics, the error in the simulation will inevitably become too large once the number of surviving photons exceeds that square-root limit. This finding is crucial because it closes a potential loophole: it confirms that if an experiment stays within this regime, a classical computer using this specific trick cannot claim to be simulating the quantum system accurately. However, the study does not stop at proving a limit; it pushes past it. The author developed a new way to simulate the experiment that does not try to replace the light itself. Instead, they kept the quantum description of the light exactly as it is and focused their approximation on the act of detection. In their method, the computer tracks the light perfectly as it travels through the maze. Only when a photon is detected does the computer make a simplifying guess about the state of the remaining light, replacing the complex quantum description with a simpler, standard shape that captures the essential features.

This shift in strategy allowed the researchers to break the square-root barrier. They showed that by approximating the detection process one click at a time, a classical computer can accurately simulate the experiment even when the number of surviving photons grows much faster than the square root of the input size. In fact, their method remains accurate when the surviving photon count grows as the two-thirds power of the input number, and under specific conditions where all light beams are treated equally, it can even reach the three-quarters power. To visualize the difference, imagine trying to predict the outcome of a game by either changing the rules of the game itself (the old method) or by making a small, calculated guess only at the moment a player scores a point (the new method). The new approach proved far more robust. The researchers tested their method on various setups, including those with just a single beam of light and more complex arrangements with multiple beams. In these tests, their new simulator consistently produced results that were closer to the true quantum behavior than the previous best methods, especially in the range of parameters relevant to current experiments.

The significance of this work lies in its ability to redefine the boundary between what is classically simulable and what is truly quantum. By proving that the old "replace the light" strategy fails beyond a certain point, the study forces the scientific community to look for even more sophisticated ways to simulate these systems if they are to keep up. Conversely, by showing that a new, more nuanced strategy can go further, it suggests that the threshold for claiming a quantum advantage might need to be set even higher. The researchers did not claim to have solved the problem of simulating all possible quantum light experiments; rather, they provided a rigorous proof that a specific, widely used approximation method has a hard limit, and they offered a new tool that extends the reach of classical simulation well beyond that limit. This refinement is essential for the field, as it helps experimentalists understand exactly how much light loss their devices can tolerate before the results become too easy for classical computers to mimic, ensuring that future claims of quantum advantage are built on solid, unassailable ground.

Technical Summary: Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root Regime

Problem Statement
Gaussian Boson Sampling (GBS) utilizes squeezed light, passive optics, and photon-number-resolving (PNR) detection to probe quantum interference, serving as a basis for photonic quantum advantage experiments. However, photon loss is a dominant experimental imperfection that significantly reduces the computational cost of classical simulation. Previous work established that for lossy GBS with fixed squeezing and accuracy, classical simulation via "classical-light replacement" (approximating the lossy input state with a classical Gaussian state) remains accurate only when the mean number of surviving photons ( $N_{out}$ ) grows no faster than the square root of the number of squeezed inputs ( $N$ ). Specifically, this regime corresponds to $N_{out} = O(\sqrt{N})$ . The central question addressed by this work is whether this square-root scaling represents a fundamental limit for all classical-light replacement methods, including those using non-Gaussian or correlated classical references, and whether the simulation regime can be extended beyond this barrier.

Methodology
The paper employs two distinct theoretical approaches to analyze and simulate lossy GBS:

Lower Bound Analysis for Classical-Light Replacement: The author investigates the limitations of replacing the quantum input state with any state possessing a non-negative Glauber–Sudarshan $P$ representation (which includes classical mixtures of coherent states, Gaussian or non-Gaussian). They construct a specific family of interferometers (the "pair family") where inputs are processed through beam splitters to create two-mode squeezed vacuum pairs. By analyzing the photon count statistics of these pairs, they demonstrate a fundamental constraint on classical count probabilities that lossy quantum states violate.
Detection Approximation Algorithm: To surpass the square-root barrier, the author proposes a simulation method that approximates the detection process rather than the input state.
- Exact Evolution: The quantum state evolves exactly between detection events.
- Conditional Reset: Upon a photon detection (a "click"), the exact non-Gaussian conditional state is replaced by a centered Gaussian state that shares the same covariance matrix.
- Trajectory Simulation: The algorithm models PNR detection as a fictitious absorption process where photons are removed one by one. The covariance matrix is updated deterministically between clicks (damping) and stochastically at clicks (photon subtraction).
- Error Control: The method bounds the total variation (TV) distance between the exact distribution and the sampled distribution by tracking the accumulated error of these Gaussian resets.

A secondary construction is introduced for the specific case where all input modes are equally squeezed ( $M=N$ ). This method utilizes an exact decomposition of the target state into a pure squeezed core followed by quantum-limited amplifiers, sampling the number of "pairs" from a negative binomial distribution and assigning them to output modes.

Key Contributions and Results

Proof of the Square-Root Limit for Classical Light: Theorem 1 establishes that for the constructed family of interferometers, any classical-light replacement (even with non-Gaussian, correlated references) incurs a total variation error of at least $1 - e^{-c_r N \eta^2}$ . This proves that the square-root regime ( $N_{out} = O(\sqrt{N})$ ) is a hard limit for input-replacement methods in the worst case. No classical reference can improve this scaling for all interferometers.
Extension to the $N^{2/3}$ Regime: Theorem 2 presents a randomized classical algorithm with polynomial expected arithmetic cost that approximates the detection process. The author proves that the total variation error is bounded by $O(N \eta^3)$ . Consequently, at fixed accuracy and squeezing, the mean surviving photon number can scale as $N_{out} = O(N^{2/3})$ . This represents a significant improvement over the $O(\sqrt{N})$ limit.
Extension to the $N^{3/4}$ Regime: For the specific case of equally squeezed inputs ( $M=N$ ), a "pair construction" based on amplifier decomposition achieves an error bound of $O(\sqrt{N}\eta^2)$ , allowing the mean surviving photon number to scale as $N_{out} = O(N^{3/4})$ .
Empirical Performance: Numerical simulations on single-mode and few-mode examples (including random interferometers) show that the combined sampler (incorporating exact input decomposition from prior work with the detection approximation) yields lower empirical error than the standard classical Gaussian reference at parameter values motivated by current experiments (e.g., squeezing $r \approx 1$ and transmission $\eta \approx 0.5$ ).

Significance and Claims
The paper claims to provide a direct separation between the capabilities of classical-light replacement methods and detection-approximation methods on the same target family. While classical-light methods become asymptotically maximally distant from the target distribution as $N \to \infty$ within the $N^{2/3}$ regime, the proposed detection-approximation sampler maintains vanishing error.

The author emphasizes that their results do not constitute a complexity-theoretic lower bound on the hardness of GBS in general, nor do they rule out tensor-network methods (which retain non-classical components). Instead, the work establishes a specific limit for the class of algorithms that replace the input with a classical state. The detection approximation method demonstrates that photon counting statistics, which cannot be approximated by classical light beyond the square-root scale, can nevertheless be approximated efficiently on a classical computer up to the $N^{2/3}$ (or $N^{3/4}$ ) scale.

The paper remains modest regarding the ultimate limits of polynomial simulation, noting that whether $N^{2/3}$ or $N^{3/4}$ represents the true boundary depends on unproven hardness assumptions. Furthermore, the author acknowledges that for current large-scale experiments (e.g., $N=1024$ , $\eta \approx 0.5$ ), the theoretical bound provided by their method may still be trivial, though the empirical performance suggests practical utility in specific regimes.

More like this