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

Simulating lossy Gaussian boson sampling with matrix-product operators

Minzhao Liu, Changhun Oh, Junyu Liu, Liang Jiang, Yuri Alexeev

Published Nov 13, 2023• 23 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.108.052604

Related papers

Classical simulation of lossy boson sampling using matrix product operators

Changhun Oh, Kyungjoo Noh, Bill Fefferman +1 more

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.

arXiv:2101.11234•Physical Review A•Aug 5, 2021•45 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

Robust quantum computational advantage with programmable 3050-photon Gaussian boson sampling

Hua-Liang Liu, Su, Hao, Si-Qiu Gong +34 more

The creation of large-scale, high-fidelity quantum computers is not only a fundamental scientific endeavour in itself, but also provides increasingly robust proofs of quantum computational advantage (QCA) in the presence of unavoidable noise and the dynamic competition with classical algorithm improvements. To overcome the biggest challenge of photon-based QCA experiments, photon loss, we report new Gaussian boson sampling (GBS) experiments with 1024 high-efficiency squeezed states injected into a hybrid spatial-temporal encoded, 8176-mode, programmable photonic quantum processor, Jiuzhang 4.0, which produces up to 3050 photon detection events. Our experimental results outperform all classical spoofing algorithms, particularly the matrix product state (MPS) method, which was recently proposed to utilise photon loss to reduce the classical simulation complexity of GBS. Using the state-of-the-art MPS algorithm on the most powerful supercomputer EI Capitan, it would take > $10^{42}$ years to construct the required tensor network for simulation, while our Jiuzhang 4.0 quantum computer takes 25.6 $μ$s to produce a sample. This work establishes a new frontier of QCA and paves the way to fault-tolerant photonic quantum computing hardware.

arXiv:2508.09092•Aug 12, 2025•6 citations

Gaussian boson sampling: Benchmarking quantum advantage

Ned Goodman, Alexander S. Dellios, Margaret D. Reid +1 more

Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.

quant-pharXiv:2604.12330•Apr 15, 2026•0 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

Gaussian boson sampling with 1,024 squeezed states in 8,176 modes

H C Liu, Hao Su, Yu-Hao Deng +34 more

Abstract The creation of large-scale, high-fidelity quantum computers is not only a fundamental scientific endeavour in itself, but also provides increasingly robust proofs of quantum computational advantage (QCA) in the presence of unavoidable noise and the dynamic competition with classical algorithm improvements. To overcome the biggest challenge of photon-based QCA experiments, photon loss, we report new Gaussian boson sampling(GBS) experiments with 1024 high-efficiency squeezed states injected into a hybrid spatial-temporal encoded, 8176-mode, programmable photonic quantum processor, Jiuzhang 4.0, which produces up to 3050 photon detection events. Our experimental results outperform all classical spoofing algorithms, particularly the matrix product state (MPS) method, which was recently proposed to utilise photon loss to reduce the classical simulation complexity of GBS. Using the state-of-the-art MPS algorithm on the most powerful supercomputer EI Capitan, it would take > 10^42 years to construct the required tensor network for simulation, while our Jiuzhang 4.0 quantum computer takes 25.6 μs to produce a sample. This work establishes a new frontier of QCA and paves the way to fault-tolerant photonic quantum computing hardware.

Nature•May 13, 2026•4 citations
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 Nout\ensuremath∝N{N}_{\text{out}}\ensuremath{\propto}\sqrt{N}Nout​\ensuremath∝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.
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.
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.
The creation of large-scale, high-fidelity quantum computers is not only a fundamental scientific endeavour in itself, but also provides increasingly robust proofs of quantum computational advantage (QCA) in the presence of unavoidable noise and the dynamic competition with classical algorithm improvements. To overcome the biggest challenge of photon-based QCA experiments, photon loss, we report new Gaussian boson sampling (GBS) experiments with 1024 high-efficiency squeezed states injected into a hybrid spatial-temporal encoded, 8176-mode, programmable photonic quantum processor, Jiuzhang 4.0, which produces up to 3050 photon detection events. Our experimental results outperform all classical spoofing algorithms, particularly the matrix product state (MPS) method, which was recently proposed to utilise photon loss to reduce the classical simulation complexity of GBS. Using the state-of-the-art MPS algorithm on the most powerful supercomputer EI Capitan, it would take > 104210^{42}1042 years to construct the required tensor network for simulation, while our Jiuzhang 4.0 quantum computer takes 25.6 μμμs to produce a sample. This work establishes a new frontier of QCA and paves the way to fault-tolerant photonic quantum computing hardware.
Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.
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.
Abstract The creation of large-scale, high-fidelity quantum computers is not only a fundamental scientific endeavour in itself, but also provides increasingly robust proofs of quantum computational advantage (QCA) in the presence of unavoidable noise and the dynamic competition with classical algorithm improvements. To overcome the biggest challenge of photon-based QCA experiments, photon loss, we report new Gaussian boson sampling(GBS) experiments with 1024 high-efficiency squeezed states injected into a hybrid spatial-temporal encoded, 8176-mode, programmable photonic quantum processor, Jiuzhang 4.0, which produces up to 3050 photon detection events. Our experimental results outperform all classical spoofing algorithms, particularly the matrix product state (MPS) method, which was recently proposed to utilise photon loss to reduce the classical simulation complexity of GBS. Using the state-of-the-art MPS algorithm on the most powerful supercomputer EI Capitan, it would take > 10^42 years to construct the required tensor network for simulation, while our Jiuzhang 4.0 quantum computer takes 25.6 μs to produce a sample. This work establishes a new frontier of QCA and paves the way to fault-tolerant photonic quantum computing hardware.