Metraipolis › archive › dc_e06d82cf3762
Efficient classical algorithm for estimating linear statistics of Boson Sampling — arXiv:2609.35447
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35447
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:45:34.628Z
- SHA-256 of the archived text
1e0029e67bf9456f121fa7c43df0a8b63ea6cbf96468627e53f9061b2eb74104- Stable URL of this page
https://metraipolis.com/documento/dc_e06d82cf3762
How to cite
Efficient classical algorithm for estimating linear statistics of Boson Sampling — arXiv:2609.35447 — arXiv (en), https://arxiv.org/abs/2609.35447 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e06d82cf3762 (Metraipolis archive dc_e06d82cf3762, sha256 1e0029e67bf9456f121fa7c43df0a8b63ea6cbf96468627e53f9061b2eb74104)
BibTeX
@misc{dce06d82cf3762,
title = {Efficient classical algorithm for estimating linear statistics of Boson Sampling — arXiv:2609.35447},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35447},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e06d82cf3762; sha256 1e0029e67bf9456f121fa7c43df0a8b63ea6cbf96468627e53f9061b2eb74104},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35447. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions. Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-29 in quant-ph). Categorie arXiv: Quantum Physics (quant-ph). Pagina del lavoro: https://arxiv.org/abs/2609.35447 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-08T00:19:23.506Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).