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:1712.10037 · Quantum

Simulating boson sampling in lossy architectures

Raúl García−Patrón, Jelmer J. Renema, V. S. Shchesnovich

Published Aug 5, 2019• 103 citations
arXivHTMLPDF

Abstract

Photon losses are among the strongest imperfections affecting multi-photon interference. Despite their importance, little is known about their effect on boson sampling experiments. In this work we show that using classical computers, one can efficiently simulate multi-photon interference in all architectures that suffer from an exponential decay of the transmission with the depth of the circuit, such as integrated photonic circuits or optical fibers. We prove that either the depth of the circuit is large enough that it can be simulated by thermal noise with an algorithm running in polynomial time, or it is shallow enough that a tensor network simulation runs in quasi-polynomial time. This result suggests that in order to implement a quantum advantage experiment with single-photons and linear optics new experimental platforms may be needed.

DOI
10.22331/q-2019-08-05-169

Related papers

Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions

Haoyu Qi, Diego Cifuentes, Kamil Brádler +3 more

Gaussian boson sampling is a candidate model for demonstrating quantum computational advantage in photonic systems. Here, the authors narrow down the range of possible architectures for such a demonstration, by introducing a classical algorithm that can simulate optical systems with shallow-depth circuits and local gates in polynomial time.

Physical Review A•May 6, 2022•12 citations

Experimental simulation of solution to boson sampling based on classical electronic circuits with exponential frequency bandwidth

Zhenwei Yang, Jiacheng Bao, H. J. Sun +1 more

A Boson sampling device is believed to be a specific quantum computer which is more efficient than its classical counterpart. Recently, a number of experimental realizations have been reported, all were based on multi-photon interference in multimode interferometers. Because of the probabilistic nature of single photons, the technique of coincidence counting has to be used in these schemes, it remains a great challenge to scale up the number of photons. Here, we present a novel way to simulate the solution of the boson sampling problem based on classical electronic circuits. Although an exponential frequency bandwidth is used, thus limiting the scalability of the scheme, the running time of our scheme is equivalent to those based on quantum optics. It is also notable that our method has good stability of classical circuits. In addition, some other related problems, which are computationally hard for classical computers, can also be simulated using our scheme. Thus, our findings are advantageous for information processing in the era of big data.

Europhysics Letters (EPL)•Oct 2, 2018•2 citations

Classical Simulation of Boson Sampling Based on Graph Structure

Changhun Oh, Youngrong Lim, Bill Fefferman +1 more

Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In this Letter, we present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit. The algorithms' complexity grows as so-called treewidth, which is closely related to the connectivity of a given linear-optical circuit. Using the algorithms, we study approximated simulations for local Haar-random linear-optical circuits. For equally spaced initial sources, we show that, when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error. Notably, right after this depth, photons start to interfere each other and the algorithms' complexity becomes subexponential in the number of sources, implying that there is a sharp transition of its complexity. Finally, when a circuit is sufficiently deep enough for photons to typically propagate to all modes, the complexity becomes exponential as generic sampling algorithms. We numerically implement a likelihood test with a recent Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.

arXiv:2110.01564•Physical Review Letters•May 13, 2022•40 citations

Classical simulability of noisy boson sampling

Jelmer J. Renema, V. S. Shchesnovich, Raúl García−Patrón

Quantum mechanics promises computational powers beyond the reach of classical computers. Current technology is on the brink of an experimental demonstration of the superior power of quantum computation compared to classical devices. For such a demonstration to be meaningful, experimental noise must not affect the computational power of the device; this occurs when a classical algorithm can use the noise to simulate the quantum system. In this work, we demonstrate an algorithm which simulates boson sampling, a quantum advantage demonstration based on many-body quantum interference of indistinguishable bosons, in the presence of optical loss. Finding the level of noise where this approximation becomes efficient lets us map out the maximum level of imperfections at which it is still possible to demonstrate a quantum advantage. We show that current photonic technology falls short of this benchmark. These results call into question the suitability of boson sampling as a quantum advantage demonstration.

arXiv:1809.01953•Sep 6, 2018•29 citations

On computational complexity and average-case hardness of shallow-depth boson sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

Boson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.

arXiv:2405.01786•Quantum•Mar 13, 2026•1 citation

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
Photon losses are among the strongest imperfections affecting multi-photon interference. Despite their importance, little is known about their effect on boson sampling experiments. In this work we show that using classical computers, one can efficiently simulate multi-photon interference in all architectures that suffer from an exponential decay of the transmission with the depth of the circuit, such as integrated photonic circuits or optical fibers. We prove that either the depth of the circuit is large enough that it can be simulated by thermal noise with an algorithm running in polynomial time, or it is shallow enough that a tensor network simulation runs in quasi-polynomial time. This result suggests that in order to implement a quantum advantage experiment with single-photons and linear optics new experimental platforms may be needed.
A Boson sampling device is believed to be a specific quantum computer which is more efficient than its classical counterpart. Recently, a number of experimental realizations have been reported, all were based on multi-photon interference in multimode interferometers. Because of the probabilistic nature of single photons, the technique of coincidence counting has to be used in these schemes, it remains a great challenge to scale up the number of photons. Here, we present a novel way to simulate the solution of the boson sampling problem based on classical electronic circuits. Although an exponential frequency bandwidth is used, thus limiting the scalability of the scheme, the running time of our scheme is equivalent to those based on quantum optics. It is also notable that our method has good stability of classical circuits. In addition, some other related problems, which are computationally hard for classical computers, can also be simulated using our scheme. Thus, our findings are advantageous for information processing in the era of big data.
Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In this Letter, we present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit. The algorithms' complexity grows as so-called treewidth, which is closely related to the connectivity of a given linear-optical circuit. Using the algorithms, we study approximated simulations for local Haar-random linear-optical circuits. For equally spaced initial sources, we show that, when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error. Notably, right after this depth, photons start to interfere each other and the algorithms' complexity becomes subexponential in the number of sources, implying that there is a sharp transition of its complexity. Finally, when a circuit is sufficiently deep enough for photons to typically propagate to all modes, the complexity becomes exponential as generic sampling algorithms. We numerically implement a likelihood test with a recent Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.
Quantum mechanics promises computational powers beyond the reach of classical computers. Current technology is on the brink of an experimental demonstration of the superior power of quantum computation compared to classical devices. For such a demonstration to be meaningful, experimental noise must not affect the computational power of the device; this occurs when a classical algorithm can use the noise to simulate the quantum system. In this work, we demonstrate an algorithm which simulates boson sampling, a quantum advantage demonstration based on many-body quantum interference of indistinguishable bosons, in the presence of optical loss. Finding the level of noise where this approximation becomes efficient lets us map out the maximum level of imperfections at which it is still possible to demonstrate a quantum advantage. We show that current photonic technology falls short of this benchmark. These results call into question the suitability of boson sampling as a quantum advantage demonstration.
Boson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.
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.