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:2101.11234 · Physical Review A

Classical simulation of lossy boson sampling using matrix product operators

Changhun Oh, Kyungjoo Noh, Bill Fefferman, Liang Jiang

Published Aug 5, 2021• 45 citations
arXivHTMLPDF

Abstract

Characterizing the computational advantage from noisy intermediate-scale quantum (NISQ) devices is an important task from theoretical and practical perspectives. Here, we numerically investigate the computational power of NISQ devices focusing on boson sampling, one of the well-known promising problems which can exhibit quantum supremacy. We study hardness of lossy boson sampling using matrix product operator (MPO) simulation to address the effect of photon loss on classical simulability using MPO entanglement entropy (EE), which characterizes a running time of an MPO algorithm. An advantage of MPO simulation over other classical algorithms proposed to date is that its simulation accuracy can be efficiently controlled by increasing an MPO's bond dimension. Notably, we show by simulating lossy boson sampling using an MPO that as an input photon number grows, its computational cost, or MPO EE, behaves differently depending on a loss scaling, exhibiting a different feature from that of lossless boson sampling. Especially when an output photon number scales faster than the square root of an input photon number, our study shows an exponential scaling of time complexity for MPO simulation. On the contrary, when an output photon number scales slower than the square root of an input photon number, MPO EE may decrease, indicating that an exponential time complexity might not be necessary.

DOI
10.1103/physreva.104.022407

Related papers

Simulating lossy Gaussian boson sampling with matrix-product operators

Minzhao Liu, Changhun Oh, Junyu Liu +2 more

Gaussian boson sampling, a computational model that is widely believed to admit quantum supremacy, has already been experimentally demonstrated and is claimed to surpass the classical simulation capabilities of even the most powerful supercomputers today. However, whether the current approach limited by photon loss and noise in such experiments prescribes a scalable path to quantum advantage is an open question. To understand the effect of photon loss on the scalability of Gaussian boson sampling, we analytically derive the asymptotic operator entanglement entropy scaling, which relates to the simulation complexity. As a result, we observe that efficient tensor network simulations are likely possible under the ${N}_{\text{out}}\ensuremath{\propto}\sqrt{N}$ scaling of the number of surviving photons ${N}_{\text{out}}$ in the number of input photons $N$. We numerically verify this result using a tensor network algorithm with $\mathrm{U}(1)$ symmetry, and we overcome previous challenges due to the large local Hilbert-space dimensions in Gaussian boson sampling with hardware acceleration. Additionally, we observe that increasing the photon number through larger squeezing does not increase the entanglement entropy significantly. Finally, we numerically find the bond dimension necessary for fixed accuracy simulations, providing more direct evidence for the complexity of tensor networks.

arXiv:2301.12814•Physical Review A•Nov 13, 2023•23 citations

Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root Regime

Youngrong Lim

Photon loss makes Gaussian boson sampling easier to simulate classically. A standard approach replaces the lossy input by classical light, and it stays accurate while the mean number of surviving photons grows no faster than the square root of the number $N$ of squeezed inputs at fixed squeezing and accuracy. We prove that this scale is a limit of replacement by classical light. For explicit interferometers, no state with a nonnegative Glauber--Sudarshan $P$ representation, Gaussian or not and however correlated, keeps the error in the photon count distribution small beyond this scale. We then surpass this limit by approximating the detection instead of the input. The sampler evolves the state exactly between detections and, after each detection, replaces the conditional state by a Gaussian with the same covariance. For every interferometer its total variation error is $O(Nη^3)$ at polynomial expected cost, where $η$ is the photon survival probability. The mean surviving photon number can therefore grow as $N^{2/3}$ at fixed accuracy. A separate pair construction reaches $N^{3/4}$ when every input mode is equally squeezed.

quant-pharXiv:2610.06526•Oct 6, 2026•0 citations

Efficient classical simulation of noisy random quantum circuits in one dimension

Kyungjoo Noh, Liang Jiang, Bill Fefferman

Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.

arXiv:2003.13163•Quantum•Sep 11, 2020•106 citations

Input phase noise in Gaussian Boson sampling

Magdalena Parýzková, Craig S. Hamilton, Igor Jex +2 more

Gaussian boson sampling is an important protocol for testing the performance of photonic quantum simulators. As such, various noise sources have been investigated that degrade the operation of such devices. In this paper, we examine a situation with phase noise between different modes of the input state leading to dephasing of the system. This models the phase fluctuations which remain even when the mean phase is controlled. We aim to determine whether these phase-noisy input states still form a computationally difficult problem. To do this, we use Matrix Product Operators to model the system, a technique recently used to model boson sampling scenarios. Our investigation finds that the Entanglement entropy grows linearly with the number of input states even for noisy input states. This implies that, unlike boson loss, this form of experimentally relevant noise remains difficult to simulate with tensor networks and may allow for the demonstration of quantum advantage without the need for implementing the challenging task of input-state phase stabilisation.

quant-pharXiv:2512.19596•Physical Review A•Dec 23, 2025•0 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

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
Characterizing the computational advantage from noisy intermediate-scale quantum (NISQ) devices is an important task from theoretical and practical perspectives. Here, we numerically investigate the computational power of NISQ devices focusing on boson sampling, one of the well-known promising problems which can exhibit quantum supremacy. We study hardness of lossy boson sampling using matrix product operator (MPO) simulation to address the effect of photon loss on classical simulability using MPO entanglement entropy (EE), which characterizes a running time of an MPO algorithm. An advantage of MPO simulation over other classical algorithms proposed to date is that its simulation accuracy can be efficiently controlled by increasing an MPO's bond dimension. Notably, we show by simulating lossy boson sampling using an MPO that as an input photon number grows, its computational cost, or MPO EE, behaves differently depending on a loss scaling, exhibiting a different feature from that of lossless boson sampling. Especially when an output photon number scales faster than the square root of an input photon number, our study shows an exponential scaling of time complexity for MPO simulation. On the contrary, when an output photon number scales slower than the square root of an input photon number, MPO EE may decrease, indicating that an exponential time complexity might not be necessary.
Gaussian boson sampling, a computational model that is widely believed to admit quantum supremacy, has already been experimentally demonstrated and is claimed to surpass the classical simulation capabilities of even the most powerful supercomputers today. However, whether the current approach limited by photon loss and noise in such experiments prescribes a scalable path to quantum advantage is an open question. To understand the effect of photon loss on the scalability of Gaussian boson sampling, we analytically derive the asymptotic operator entanglement entropy scaling, which relates to the simulation complexity. As a result, we observe that efficient tensor network simulations are likely possible under the ${N}_{\text{out}}\ensuremath{\propto}\sqrt{N}$ scaling of the number of surviving photons Nout{N}_{\text{out}}Nout​ in the number of input photons NNN. We numerically verify this result using a tensor network algorithm with U(1)\mathrm{U}(1)U(1) symmetry, and we overcome previous challenges due to the large local Hilbert-space dimensions in Gaussian boson sampling with hardware acceleration. Additionally, we observe that increasing the photon number through larger squeezing does not increase the entanglement entropy significantly. Finally, we numerically find the bond dimension necessary for fixed accuracy simulations, providing more direct evidence for the complexity of tensor networks.
Photon loss makes Gaussian boson sampling easier to simulate classically. A standard approach replaces the lossy input by classical light, and it stays accurate while the mean number of surviving photons grows no faster than the square root of the number NNN of squeezed inputs at fixed squeezing and accuracy. We prove that this scale is a limit of replacement by classical light. For explicit interferometers, no state with a nonnegative Glauber--Sudarshan PPP representation, Gaussian or not and however correlated, keeps the error in the photon count distribution small beyond this scale. We then surpass this limit by approximating the detection instead of the input. The sampler evolves the state exactly between detections and, after each detection, replaces the conditional state by a Gaussian with the same covariance. For every interferometer its total variation error is O(Nη3)O(Nη^3)O(Nη3) at polynomial expected cost, where ηηη is the photon survival probability. The mean surviving photon number can therefore grow as N2/3N^{2/3}N2/3 at fixed accuracy. A separate pair construction reaches N3/4N^{3/4}N3/4 when every input mode is equally squeezed.
Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.
Gaussian boson sampling is an important protocol for testing the performance of photonic quantum simulators. As such, various noise sources have been investigated that degrade the operation of such devices. In this paper, we examine a situation with phase noise between different modes of the input state leading to dephasing of the system. This models the phase fluctuations which remain even when the mean phase is controlled. We aim to determine whether these phase-noisy input states still form a computationally difficult problem. To do this, we use Matrix Product Operators to model the system, a technique recently used to model boson sampling scenarios. Our investigation finds that the Entanglement entropy grows linearly with the number of input states even for noisy input states. This implies that, unlike boson loss, this form of experimentally relevant noise remains difficult to simulate with tensor networks and may allow for the demonstration of quantum advantage without the need for implementing the challenging task of input-state phase stabilisation.
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.
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.