Classical algorithm for simulating experimental Gaussian boson sampling

Abstract

Gaussian boson sampling is a promising candidate for showing experimental quantum advantage. While there is evidence that noiseless Gaussian boson sampling is hard to efficiently simulate using a classical computer, the current Gaussian boson sampling experiments inevitably suffer from loss and other noise models. Despite a high photon loss rate and the presence of noise, they are currently claimed to be hard to classically simulate with the best-known classical algorithm. In this work, we present a classical tensor-network algorithm that simulates Gaussian boson sampling and whose complexity can be significantly reduced when the photon loss rate is high. By generalizing the existing thermal-state approximation algorithm of lossy Gaussian boson sampling, the proposed algorithm allows us to achieve increased accuracy as the running time of the algorithm scales, as opposed to the algorithm that samples from the thermal state, which can give only a fixed accuracy. This generalization enables us to simulate the largest scale Gaussian boson sampling experiment so far using relatively modest computational resources, even though the output state of these experiments is not believed to be close to a thermal state. By demonstrating that our new classical algorithm outperforms the large-scale experiments on the benchmarks used as evidence for quantum advantage, we exhibit evidence that our classical sampler can simulate the ground-truth distribution better than the experiment can, which disputes the experimental quantum advantage claims.

23 pages, 13 figures

References in corpus (27)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Matrix product states represent ground states faithfully
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Entropy scaling and simulability by Matrix Product States
• Gaussian states in continuous variable quantum information
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Computational advantage of quantum random sampling
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Mode-Wise Entanglement of Gaussian States
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• A polynomial-time classical algorithm for noisy random circuit sampling
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Classical simulation of lossy boson sampling using matrix product operators
• Franck-Condon factors by counting perfect matchings of graphs with loops
• Classical simulation of boson sampling based on graph structure
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Gaussian Noise Sensitivity and BosonSampling
• Spoofing cross entropy measure in boson sampling
• Simulating lossy Gaussian boson sampling with matrix product operators
• Classical models may be a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model
• On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
• Quantum-inspired classical algorithm for molecular vibronic spectra
• A sharp phase transition in linear cross-entropy benchmarking
• On classical simulation algorithms for noisy Boson Sampling

Cited by in corpus (21)

• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Tensor networks for quantum computing
• Quantum algorithms for scientific computing
• Quantum learning advantage on a scalable photonic platform
• Classical simulability of constant-depth linear-optical circuits with noise
• Validation of a noisy Gaussian boson sampler via graph theory
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• Configurable photonic simulator for quantum field dynamics
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
• Classical simulation of circuits with realistic odd-dimensional Gottesman-Kitaev-Preskill states
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Boundaries for quantum advantage with single photons and loop-based time-bin interferometers
• Resourcefulness of non-classical continuous-variable quantum gates
• Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond
• Tensorization of neural networks for improved privacy and interpretability
• Optical Quantum Computing
• Maximum heralding probabilities of nonclassical-state generation from a two-mode Gaussian state via photon-counting measurements
• Realistic photon-number resolution in Gaussian boson sampling
• Boosting Gaussian Boson Sampling using Optical Parametric Amplification Networks
• Classical algorithms for measurement-adaptive Gaussian circuits