PaperfootJoin free
arXiv

Photon sampling with fixed-fraction loss admits efficient simulation

The proof covers any fixed surviving share of photons and most randomly chosen optical networks, with an approximation whose error can be made arbitrarily small.

Paper by Byeongseon Go, Hyunseok Jeong
Figure 1. Illustration of two representative photon-loss models for BosonSampling.
Open the figure at full size
Figure 1. Illustration of two representative photon-loss models for BosonSampling.Illustration of two representative photon-loss models for BosonSampling.Go et al.
Preprint: method

Edited by Boris Djordjevic · Paperfoot

Paper

The researchers proved guarantees for a new algorithm that approximately simulated lossy BosonSampling on ordinary computers for randomly chosen optical networks. BosonSampling is a task that samples detection patterns of photons sent through a network that mixes their paths.

In the main model, a fixed number of photons was lost uniformly at random. The proof covered any fixed surviving fraction strictly between zero and one. It bounded both the approximation error and the chance of failure over randomly chosen networks. Runtime had a polynomial bound: it grew no faster than fixed powers of network size, photon count and the inverses of the allowed error and failure probability. The researchers also proved an analogous result when each photon had the same fixed transmission probability, strictly between zero and one.

Why it matters

The proof extends the known conditions under which ordinary computers can simulate this quantum sampling task. It shows that retaining a fixed share of photons can still permit efficient classical simulation under the models considered.

Caveats

The guarantees concern a specified mathematical distribution of random optical networks, not every network. The work is a preprint; its abstract reports no measured runtimes, so the theoretical efficiency guarantee does not establish practical speed.

In this paper

classical simulation of lossy BosonSampling

Methods
randomized classical algorithm (this paper)

What it shows

Under the dilute-mode condition, a randomized classical algorithm samples from a distribution within total variation distance ε of the collision-collapsed fixed-loss BosonSampling distribution with runtime MnN^3 ε^-2 δ^-1 2^O(d) for at least a 1-δ fraction of

Then there exists a randomized classical algorithm that, for at least a 1-\delta fraction of Haar-random interferometers, samples from a distribution within total variation distance \varepsilon of the collision-collapsed fixed-loss BosonSampling distribution, with runtime MnN^{3}\varepsilon^{-2}\delta^{-1}2^{O(d …

Theorem 1 (Informal).

The algorithm runs in polynomial time for every fixed surviving fraction in the linear-survival regime.

For every fixed surviving fraction n/N\in(0,1), the algorithm of Theorem 1 runs in time \operatorname{poly}(M,N,\varepsilon^{-1},\delta^{-1}).

Corollary 1 (Polynomial-time simulability in the linear-survival regime).

Under an additional mode-number condition, the collision-collapsed sampler yields a full fixed-loss Fock-output approximation guarantee while preserving asymptotically the same runtime, accuracy, and success-probability guarantees.

Under the additional mode-number condition M=\Omega(n^{2}/(\varepsilon\delta)), the collision-collapsed sampler of Theorem 1 yields a full fixed-loss Fock-output approximation guarantee, while preserving asymptotically the same runtime, accuracy, and success-probability guarantees.

Corollary 2 (Full Fock-output approximation).

For the uniform-transmission-loss model, the results imply polynomial-time classical simulability for every fixed transmission probability under the dilute-mode condition.

For the uniform-transmission-loss model, where each of the N photons is independently transmitted with probability \eta, Theorem 1 implies polynomial-time classical simulability for every fixed transmission probability \eta\in(0,1) under the stated dilute-mode condition.

Corollary 3 (Uniform-transmission loss).

Quoted word for word from the full text on arXiv.

The paper

Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss

Byeongseon Go, Hyunseok Jeong

arXiv, Oct 19, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.27065

arXiv:2610.27065v1 in quant-ph

AbstractPDFHTML

Comments: 33 pages, 3 figures

Cite as BibTeX
@misc{go2026polynomialtime,
  title = {Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss},
  author = {Go, Byeongseon and Jeong, Hyunseok},
  year = {2026},
  eprint = {2610.27065},
  archivePrefix = {arXiv},
  primaryClass = {quant-ph},
  doi = {10.48550/arxiv.2610.27065},
  url = {https://arxiv.org/abs/2610.27065}
}

Related