Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Classical sampling from noisy boson sampling and negative probabilities

V. S. Shchesnovich

Published Mar 12, 2024• 0 citations
Publisher

Abstract

It is known that, by accounting for the multiboson interferences up to a finite order, the output distribution of noisy boson sampling, with distinguishability of bosons serving as noise, can be approximately sampled from in a time polynomial in the total number of bosons. The drawback of this approach is that the joint probabilities of completely distinguishable bosons, i.e., those that do not interfere at all, have to be computed also. In trying to restore the ability to sample from the distinguishable bosons with computation of only the single-boson probabilities, one faces the following issue: the quantum probability factors in a convex-sum expression, if truncated to a finite order of multiboson interference, have, on average, a finite amount of negativity in a random interferometer. The truncated distribution does become a proper one, while allowing for sampling from it in a polynomial time, only in a vanishing domain close to the completely distinguishable bosons. Nevertheless, the conclusion that the negativity issue is inherent to all efficient classical approximations to noisy boson sampling may be premature. I outline the direction for an enitre new program, which seems to point to a solution. However, its success depends on the asymptotic behavior of the symmetric group characters, which is not known.

DOI
10.1103/physreva.109.032610

Related papers

Classical sampling from noisy Boson Sampling and the negative probabilities

V. S. Shchesnovich

It is known that, by accounting for the multiboson interferences up to a finite order, the output distribution of noisy Boson Sampling, with distinguishability of bosons serving as noise, can be approximately sampled from in a time polynomial in the total number of bosons. The drawback of this approach is that the joint probabilities of completely distinguishable bosons, i.e., those that do not interfere at all, have to be computed also. In trying to restore the ability to sample from the distinguishable bosons with computation of only the single-boson probabilities, one faces the following issue: the quantum probability factors in a convex-sum expression, if truncated to a finite order of multiboson interference, have, on average, a finite amount of negativity in a random interferometer. The truncated distribution does become a proper one, while allowing for sampling from it in a polynomial time, only in a vanishing domain close to the completely distinguishable bosons. Nevertheless, the conclusion that the negativity issue is inherent to all efficient classical approximations to noisy Boson Sampling may be premature. I outline the direction for a whole new program, which seem to point to a solution. However its success depends on the asymptotic behavior of the symmetric group characters, which is not known.

arXiv:2307.05344•Jul 11, 2023•0 citations

Distinguishing noisy boson sampling from classical simulations

V. S. Shchesnovich

Giving a convincing experimental evidence of the quantum supremacy over classical simulations is a challenging goal. Noise is considered to be the main problem in such a demonstration, hence it is urgent to understand the effect of noise. Recently found classical algorithms can efficiently approximate, to any small error, the output of boson sampling with finite-amplitude noise. In this work it is shown analytically and confirmed by numerical simulations that one can efficiently distinguish the output distribution of such a noisy boson sampling from the approximations accounting for low-order quantum multiboson interferences, what includes the mentioned classical algorithms. The number of samples required to tell apart the quantum and classical output distributions is strongly affected by the previously unexplored parameter: density of bosons, i.e., the ratio of total number of interfering bosons to number of input ports of interferometer. Such critical dependence is strikingly reminiscent of the quantum-to-classical transition in systems of identical particles, which sets in when the system size scales up while density of particles vanishes.

arXiv:1905.11458•Quantum•Mar 29, 2021•19 citations

On classical simulation algorithms for noisy Boson Sampling

Changhun Oh, Liang Jiang, Bill Fefferman

We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This algorithm is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai and Kindler that the output probability of Boson Sampling experiments with a Gaussian noise model can be approximated by sparse low-degree polynomials. This observation alone does not suffice for classical sampling, because its marginal probabilities might not be approximated by sparse low-degree polynomials, and furthermore, the approximated probabilities might be negative. We solve this problem by employing the first quantization representation to give an algorithm for computing the marginal probabilities of these experiments. We prove that when the overall noise rate is constant, the algorithm runs in time quasi-polynomial in the number of input photons $N$ and accuracy. When the overall noise rate scales as $1-x_1^γ$ for constant $x_1$ and $γ=Ω(\log N)$, the running time becomes polynomial. Furthermore, we study noisy Boson Sampling with practically relevant noise models such as partial distinguishability and photon loss. We show that the same technique does not immediately apply in these settings, leaving open the possibility of a scalable demonstration of noisy quantum advantage for these noise models in certain parameter regimes.

arXiv:2301.11532•Jan 27, 2023•3 citations

Boson sampling cannot be faithfully simulated by only the lower-order multi-boson interferences

V. S. Shchesnovich

To simulate noisy boson sampling approximating it by only the lower-order multi-boson interferences (e.g., by a smaller number of interfering bosons and classical particles) is very popular idea. I show that the output data from any such classical simulations can be efficiently distinguished from that of the quantum device they try to simulate, even with finite noise in the latter. The distinguishing datasets can be the experimental estimates of some large probabilities, a wide class of such is presented. This is a sequel of \textit{Quantum} \textbf{5}, 423 (2021), where I present more accessible account of the main result enhanced by additional insight on the contribution from the higher-order multi-boson interferences in presence of noise.

arXiv:2204.07792•Apr 16, 2022•2 citations

On the classical complexity of sampling from quantum interference of indistinguishable bosons

V. S. Shchesnovich

Experimental demonstration of the quantum advantage over classical simulations with Boson Sampling is currently under intensive investigation. There seems to be a scalability issue to the necessary number of bosons on the linear optical platforms and the experiments, such as the recent Boson Sampling with 20 photons on 60-port interferometer by H. Wang et al., Phys. Rev. Lett.123 (2019) 250503, are usually carried out on a small interferometer, much smaller than the size necessary for the no-collision regime. Before demonstration of quantum advantage, it is urgent to estimate exactly how the classical computations necessary for sampling from the output distribution of Boson Sampling are reduced when a smaller-size interferometer is used. This work supplies such a result, valid with arbitrarily close to 1 probability, which reduces in the no-collision regime to the previous estimate by Clifford and Clifford. One of the results with immediate application to current experiments with Boson Sampling is that classically sampling from the interference of [Formula: see text] single bosons on an [Formula: see text]-port interferometer is at least as hard as that with [Formula: see text] single bosons in the no-collision regime, i.e. on a much larger interferometer with at least [Formula: see text] ports.

arXiv:1904.02013•International Journal of Quantum Information•Oct 1, 2020•11 citations

Noise in boson sampling and the threshold of efficient classical simulatability

V. S. Shchesnovich

We study the quantum to classical transition in boson sampling by analyzing how $N$-boson interference is affected by inevitable noise in an experimental setup. We adopt the Gaussian noise model of Kalai and Kindler for boson sampling and show that it appears from some realistic experimental imperfections. We reveal a connection between noise in boson sampling and partial distinguishability of bosons, which allows us to prove efficient classical simulatability of noisy no-collision boson sampling with finite noise amplitude $\ensuremath{\epsilon}$, i.e., $\ensuremath{\epsilon}=\mathrm{\ensuremath{\Omega}}(1)$ as $N\ensuremath{\rightarrow}\ensuremath{\infty}$. On the other hand, using an equivalent representation of network noise as losses of bosons compensated by random (dark) counts of detectors, it is proven that for noise amplitude inversely proportional to total number of bosons, i.e., $\ensuremath{\epsilon}=O(1/N)$, noisy no-collision boson sampling is as hard to simulate classically as in the noiseless case. Moreover, the ratio of ``noise clicks'' (lost bosons compensated by dark counts) to the total number of bosons $N$ vanishes as $N\ensuremath{\rightarrow}\ensuremath{\infty}$ for arbitrarily small noise amplitude, i.e., $\ensuremath{\epsilon}=o(1)$ as $N\ensuremath{\rightarrow}\ensuremath{\infty}$; hence, we conjecture that such a noisy boson sampling is also hard to simulate classically. The results significantly relax the sufficient condition on noise in network components, such as two-mode beam splitters, for classical hardness of experimental boson sampling

arXiv:1902.02258•Physical Review A•Jul 24, 2019•31 citations
It is known that, by accounting for the multiboson interferences up to a finite order, the output distribution of noisy boson sampling, with distinguishability of bosons serving as noise, can be approximately sampled from in a time polynomial in the total number of bosons. The drawback of this approach is that the joint probabilities of completely distinguishable bosons, i.e., those that do not interfere at all, have to be computed also. In trying to restore the ability to sample from the distinguishable bosons with computation of only the single-boson probabilities, one faces the following issue: the quantum probability factors in a convex-sum expression, if truncated to a finite order of multiboson interference, have, on average, a finite amount of negativity in a random interferometer. The truncated distribution does become a proper one, while allowing for sampling from it in a polynomial time, only in a vanishing domain close to the completely distinguishable bosons. Nevertheless, the conclusion that the negativity issue is inherent to all efficient classical approximations to noisy boson sampling may be premature. I outline the direction for an enitre new program, which seems to point to a solution. However, its success depends on the asymptotic behavior of the symmetric group characters, which is not known.
It is known that, by accounting for the multiboson interferences up to a finite order, the output distribution of noisy Boson Sampling, with distinguishability of bosons serving as noise, can be approximately sampled from in a time polynomial in the total number of bosons. The drawback of this approach is that the joint probabilities of completely distinguishable bosons, i.e., those that do not interfere at all, have to be computed also. In trying to restore the ability to sample from the distinguishable bosons with computation of only the single-boson probabilities, one faces the following issue: the quantum probability factors in a convex-sum expression, if truncated to a finite order of multiboson interference, have, on average, a finite amount of negativity in a random interferometer. The truncated distribution does become a proper one, while allowing for sampling from it in a polynomial time, only in a vanishing domain close to the completely distinguishable bosons. Nevertheless, the conclusion that the negativity issue is inherent to all efficient classical approximations to noisy Boson Sampling may be premature. I outline the direction for a whole new program, which seem to point to a solution. However its success depends on the asymptotic behavior of the symmetric group characters, which is not known.
Giving a convincing experimental evidence of the quantum supremacy over classical simulations is a challenging goal. Noise is considered to be the main problem in such a demonstration, hence it is urgent to understand the effect of noise. Recently found classical algorithms can efficiently approximate, to any small error, the output of boson sampling with finite-amplitude noise. In this work it is shown analytically and confirmed by numerical simulations that one can efficiently distinguish the output distribution of such a noisy boson sampling from the approximations accounting for low-order quantum multiboson interferences, what includes the mentioned classical algorithms. The number of samples required to tell apart the quantum and classical output distributions is strongly affected by the previously unexplored parameter: density of bosons, i.e., the ratio of total number of interfering bosons to number of input ports of interferometer. Such critical dependence is strikingly reminiscent of the quantum-to-classical transition in systems of identical particles, which sets in when the system size scales up while density of particles vanishes.
We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This algorithm is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai and Kindler that the output probability of Boson Sampling experiments with a Gaussian noise model can be approximated by sparse low-degree polynomials. This observation alone does not suffice for classical sampling, because its marginal probabilities might not be approximated by sparse low-degree polynomials, and furthermore, the approximated probabilities might be negative. We solve this problem by employing the first quantization representation to give an algorithm for computing the marginal probabilities of these experiments. We prove that when the overall noise rate is constant, the algorithm runs in time quasi-polynomial in the number of input photons NNN and accuracy. When the overall noise rate scales as 1−x1γ1-x_1^γ1−x1γ​ for constant x1x_1x1​ and γ=Ω(log⁡N)γ=Ω(\log N)γ=Ω(logN), the running time becomes polynomial. Furthermore, we study noisy Boson Sampling with practically relevant noise models such as partial distinguishability and photon loss. We show that the same technique does not immediately apply in these settings, leaving open the possibility of a scalable demonstration of noisy quantum advantage for these noise models in certain parameter regimes.
To simulate noisy boson sampling approximating it by only the lower-order multi-boson interferences (e.g., by a smaller number of interfering bosons and classical particles) is very popular idea. I show that the output data from any such classical simulations can be efficiently distinguished from that of the quantum device they try to simulate, even with finite noise in the latter. The distinguishing datasets can be the experimental estimates of some large probabilities, a wide class of such is presented. This is a sequel of \textit{Quantum} \textbf{5}, 423 (2021), where I present more accessible account of the main result enhanced by additional insight on the contribution from the higher-order multi-boson interferences in presence of noise.
Experimental demonstration of the quantum advantage over classical simulations with Boson Sampling is currently under intensive investigation. There seems to be a scalability issue to the necessary number of bosons on the linear optical platforms and the experiments, such as the recent Boson Sampling with 20 photons on 60-port interferometer by H. Wang et al., Phys. Rev. Lett.123 (2019) 250503, are usually carried out on a small interferometer, much smaller than the size necessary for the no-collision regime. Before demonstration of quantum advantage, it is urgent to estimate exactly how the classical computations necessary for sampling from the output distribution of Boson Sampling are reduced when a smaller-size interferometer is used. This work supplies such a result, valid with arbitrarily close to 1 probability, which reduces in the no-collision regime to the previous estimate by Clifford and Clifford. One of the results with immediate application to current experiments with Boson Sampling is that classically sampling from the interference of [Formula: see text] single bosons on an [Formula: see text]-port interferometer is at least as hard as that with [Formula: see text] single bosons in the no-collision regime, i.e. on a much larger interferometer with at least [Formula: see text] ports.
We study the quantum to classical transition in boson sampling by analyzing how NNN-boson interference is affected by inevitable noise in an experimental setup. We adopt the Gaussian noise model of Kalai and Kindler for boson sampling and show that it appears from some realistic experimental imperfections. We reveal a connection between noise in boson sampling and partial distinguishability of bosons, which allows us to prove efficient classical simulatability of noisy no-collision boson sampling with finite noise amplitude $\ensuremath{\epsilon}$, i.e., $\ensuremath{\epsilon}=\mathrm{\ensuremath{\Omega}}(1)$ as $N\ensuremath{\rightarrow}\ensuremath{\infty}$. On the other hand, using an equivalent representation of network noise as losses of bosons compensated by random (dark) counts of detectors, it is proven that for noise amplitude inversely proportional to total number of bosons, i.e., $\ensuremath{\epsilon}=O(1/N)$, noisy no-collision boson sampling is as hard to simulate classically as in the noiseless case. Moreover, the ratio of ``noise clicks'' (lost bosons compensated by dark counts) to the total number of bosons NNN vanishes as $N\ensuremath{\rightarrow}\ensuremath{\infty}$ for arbitrarily small noise amplitude, i.e., $\ensuremath{\epsilon}=o(1)$ as $N\ensuremath{\rightarrow}\ensuremath{\infty}$; hence, we conjecture that such a noisy boson sampling is also hard to simulate classically. The results significantly relax the sufficient condition on noise in network components, such as two-mode beam splitters, for classical hardness of experimental boson sampling