Classical simulation of boson sampling based on graph structure

Abstract

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 work, 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 sub-exponential 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.

6+22 pages, 5+6 figures

References in corpus (10)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Quantum information with Gaussian states
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Experimental Gaussian Boson Sampling
• Classical simulation of lossy boson sampling using matrix product operators
• The complexity of simulating constant-depth BosonSampling

Cited by in corpus (25)

• Computational advantage of quantum random sampling
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Classical algorithm for simulating experimental Gaussian boson sampling
• Quantum machine learning with Adaptive Boson Sampling via post-selection
• Spoofing cross entropy measure in boson sampling
• Quantum Metrological Power of Continuous-Variable Quantum Networks
• Quantum-inspired classical algorithm for molecular vibronic spectra
• Page curves and typical entanglement in linear optics
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• Certification of Gaussian Boson Sampling via graph theory
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Classical simulability of constant-depth linear-optical circuits with noise
• Approximating outcome probabilities of linear optical circuits
• Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
• High performance Boson Sampling simulation via data-flow engines
• Validation of a noisy Gaussian boson sampler via graph theory
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• 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
• Optical Quantum Computing
• Classical algorithms for measurement-adaptive Gaussian circuits
• Realistic photon-number resolution in Gaussian boson sampling
• Linear-optical protocols for mitigating and suppressing noise in bosonic systems