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

arXiv:2202.12052 · Physical Review A

Noise thresholds for classical simulability of nonlinear boson sampling

Gabriele Bressanini, Hyukjoon Kwon, M. S. Kim

Published Oct 10, 2022• 8 citations
arXivHTMLPDF

Abstract

Boson sampling, a computational problem conjectured to be hard to simulate on a classical machine, is a promising candidate for an experimental demonstration of quantum advantage using bosons. However, inevitable experimental noise and imperfections, such as loss in the interferometer and random counts at the detectors, could challenge the sampling task from entering the regime where quantum advantage is achievable. In this work we introduce higher-order nonlinearities as a means to enhance the computational complexity of the problem and the protocol's robustness against noise, i.e., to increase the noise threshold that allows us to perform an efficient classical simulation of the problem. Using a phase-space method based on the negativity volume of the relevant quasiprobability distributions, we establish a necessary nonclassicality condition that any experimental proof of quantum advantage must satisfy. Our results indicate that the addition of single-mode Kerr nonlinearity at the input-state preparation level, while retaining a linear-optical evolution, makes the boson-sampling protocol more robust against noise and consequently relaxes the constraints on the noise parameters required to show quantum advantage.

DOI
10.1103/physreva.106.042413

Related papers

Gaussian boson sampling at finite temperature

Gabriele Bressanini, Hyukjoon Kwon, M. S. Kim

Gaussian boson sampling (GBS) is a promising candidate for an experimental demonstration of quantum advantage using photons. However, sufficiently large noise might hinder a GBS implementation from entering the regime where quantum speedup is achievable. Here, we investigate how thermal noise affects the classical intractability of generic quantum optical sampling experiments, GBS being a particular instance of the latter. We do so by establishing sufficient conditions for an efficient simulation to be feasible, expressed in the form of inequalities between the relevant parameters that characterize the system and its imperfections. We demonstrate that the addition of thermal noise—modeled by (passive) linear optical interaction between the system and a Markovian thermal bath—has the effect of tightening the constraints on the remaining noise parameters, required to show quantum advantage. Furthermore, we show that there exists a threshold temperature, under the assumption of a uniform loss rate, at which quantum sampling experiments become classically simulable, and provide an intuitive physical interpretation by relating this occurrence with the disappearance of the quantum state's nonclassical properties. Published by the American Physical Society 2024

arXiv:2308.13291•Physical Review A•Jan 12, 2024•3 citations

Regimes of Classical Simulability for Noisy Gaussian Boson Sampling

Haoyu Qi, Daniel J. Brod, Nicolás Quesada +1 more

As a promising candidate for exhibiting quantum computational supremacy, Gaussian boson sampling (GBS) is designed to exploit the ease of experimental preparation of Gaussian states. However, sufficiently large and inevitable experimental noise might render GBS classically simulable. In this work, we formalize this intuition by establishing a sufficient condition for approximate polynomial-time classical simulation of noisy GBS-in the form of an inequality between the input squeezing parameter, the overall transmission rate, and the quality of photon detectors. Our result serves as a nonclassicality test that must be passed by any quantum computational supremacy demonstration based on GBS. We show that, for most linear-optical architectures, where photon loss increases exponentially with the circuit depth, noisy GBS loses its quantum advantage in the asymptotic limit. Our results thus delineate intermediate-sized regimes where GBS devices might considerably outperform classical computers for modest noise levels. Finally, we find that increasing the amount of input squeezing is helpful to evade our classical simulation algorithm, which suggests a potential route to mitigate photon loss.

arXiv:1905.12075•Physical Review Letters•Mar 13, 2020•87 citations

Sufficient Conditions for Efficient Classical Simulation of Quantum Optics

Saleh Rahimi-Keshari, Timothy C. Ralph, Carlton M. Caves

We provide general sufficient conditions for the efficient classical simulation of quantum-optics experiments that involve inputting states to a quantum process and making measurements at the output. The first condition is based on the negativity of phase-space quasiprobability distributions (PQDs) of the output state of the process and the output measurements; the second one is based on the negativity of PQDs of the input states, the output measurements, and the transition function associated with the process. We show that these conditions provide useful practical tools for investigating the effects of imperfections in implementations of boson sampling. In particular, we apply our formalism to boson-sampling experiments that use single-photon or spontaneous-parametric-down-conversion sources and on-off photodetectors. Considering simple models for loss and noise, we show that above some threshold for the probability of random counts in the photodetectors, these boson-sampling experiments are classically simulatable. We identify mode mismatching as the major source of error contributing to random counts and suggest that this is the chief challenge for implementations of boson sampling of interesting size.

arXiv:1511.06526•Physical Review X•Jun 20, 2016•152 citations

Classical Simulation of Quantum Systems?

J. D. Franson

We provide general sufficient conditions for the efficient classical simulation of quantum-optics experiments that involve inputting states to a quantum process and making measurements at the output.The first condition is based on the negativity of phase-space quasiprobability distributions (PQDs) of the output state of the process and the output measurements; the second one is based on the negativity of PQDs of the input states, the output measurements, and the transition function associated with the process.We show that these conditions provide useful practical tools for investigating the effects of imperfections in implementations of boson sampling.In particular, we apply our formalism to boson-sampling experiments that use single-photon or spontaneous-parametric-down-conversion sources and on-off photodetectors.Considering simple models for loss and noise, we show that above some threshold for the probability of random counts in the photodetectors, these boson-sampling experiments are classically simulatable.We identify mode mismatching as the major source of error contributing to random counts and suggest that this is the chief challenge for implementations of boson sampling of interesting size.

Physics•Jun 20, 2016•2 citations

Efficient classical algorithm for estimating linear statistics of Boson Sampling

Benoit Seron, Hugo Thomas, Eduardo Araujo +3 more

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.

quant-pharXiv:2609.35447•Sep 29, 2026•0 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
Boson sampling, a computational problem conjectured to be hard to simulate on a classical machine, is a promising candidate for an experimental demonstration of quantum advantage using bosons. However, inevitable experimental noise and imperfections, such as loss in the interferometer and random counts at the detectors, could challenge the sampling task from entering the regime where quantum advantage is achievable. In this work we introduce higher-order nonlinearities as a means to enhance the computational complexity of the problem and the protocol's robustness against noise, i.e., to increase the noise threshold that allows us to perform an efficient classical simulation of the problem. Using a phase-space method based on the negativity volume of the relevant quasiprobability distributions, we establish a necessary nonclassicality condition that any experimental proof of quantum advantage must satisfy. Our results indicate that the addition of single-mode Kerr nonlinearity at the input-state preparation level, while retaining a linear-optical evolution, makes the boson-sampling protocol more robust against noise and consequently relaxes the constraints on the noise parameters required to show quantum advantage.
Gaussian boson sampling (GBS) is a promising candidate for an experimental demonstration of quantum advantage using photons. However, sufficiently large noise might hinder a GBS implementation from entering the regime where quantum speedup is achievable. Here, we investigate how thermal noise affects the classical intractability of generic quantum optical sampling experiments, GBS being a particular instance of the latter. We do so by establishing sufficient conditions for an efficient simulation to be feasible, expressed in the form of inequalities between the relevant parameters that characterize the system and its imperfections. We demonstrate that the addition of thermal noise—modeled by (passive) linear optical interaction between the system and a Markovian thermal bath—has the effect of tightening the constraints on the remaining noise parameters, required to show quantum advantage. Furthermore, we show that there exists a threshold temperature, under the assumption of a uniform loss rate, at which quantum sampling experiments become classically simulable, and provide an intuitive physical interpretation by relating this occurrence with the disappearance of the quantum state's nonclassical properties. Published by the American Physical Society 2024
As a promising candidate for exhibiting quantum computational supremacy, Gaussian boson sampling (GBS) is designed to exploit the ease of experimental preparation of Gaussian states. However, sufficiently large and inevitable experimental noise might render GBS classically simulable. In this work, we formalize this intuition by establishing a sufficient condition for approximate polynomial-time classical simulation of noisy GBS-in the form of an inequality between the input squeezing parameter, the overall transmission rate, and the quality of photon detectors. Our result serves as a nonclassicality test that must be passed by any quantum computational supremacy demonstration based on GBS. We show that, for most linear-optical architectures, where photon loss increases exponentially with the circuit depth, noisy GBS loses its quantum advantage in the asymptotic limit. Our results thus delineate intermediate-sized regimes where GBS devices might considerably outperform classical computers for modest noise levels. Finally, we find that increasing the amount of input squeezing is helpful to evade our classical simulation algorithm, which suggests a potential route to mitigate photon loss.
We provide general sufficient conditions for the efficient classical simulation of quantum-optics experiments that involve inputting states to a quantum process and making measurements at the output. The first condition is based on the negativity of phase-space quasiprobability distributions (PQDs) of the output state of the process and the output measurements; the second one is based on the negativity of PQDs of the input states, the output measurements, and the transition function associated with the process. We show that these conditions provide useful practical tools for investigating the effects of imperfections in implementations of boson sampling. In particular, we apply our formalism to boson-sampling experiments that use single-photon or spontaneous-parametric-down-conversion sources and on-off photodetectors. Considering simple models for loss and noise, we show that above some threshold for the probability of random counts in the photodetectors, these boson-sampling experiments are classically simulatable. We identify mode mismatching as the major source of error contributing to random counts and suggest that this is the chief challenge for implementations of boson sampling of interesting size.
We provide general sufficient conditions for the efficient classical simulation of quantum-optics experiments that involve inputting states to a quantum process and making measurements at the output.The first condition is based on the negativity of phase-space quasiprobability distributions (PQDs) of the output state of the process and the output measurements; the second one is based on the negativity of PQDs of the input states, the output measurements, and the transition function associated with the process.We show that these conditions provide useful practical tools for investigating the effects of imperfections in implementations of boson sampling.In particular, we apply our formalism to boson-sampling experiments that use single-photon or spontaneous-parametric-down-conversion sources and on-off photodetectors.Considering simple models for loss and noise, we show that above some threshold for the probability of random counts in the photodetectors, these boson-sampling experiments are classically simulatable.We identify mode mismatching as the major source of error contributing to random counts and suggest that this is the chief challenge for implementations of boson sampling of interesting size.
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.
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