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.

arXiv comment6+22 pages, 5+6 figures

References in corpus (32)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Gaussian Quantum Information
• Quantum computational advantage using photons
• Characterizing Quantum Supremacy in Near-Term Devices
• Continuous variable quantum information: Gaussian states and beyond
• Gaussian Boson Sampling
• Simulating quantum computation by contracting tensor networks
• 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 fidelity for arbitrary Gaussian states
• A detailed study of Gaussian Boson Sampling
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Simulating boson sampling in lossy architectures
• Convergence Conditions for Random Quantum Circuits
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Regimes of classical simulability for noisy Gaussian boson sampling
• Classical simulation of photonic linear optics with lost particles
• Direct dialling of Haar random unitary matrices
• BosonSampling with Lost Photons
• Experimental Gaussian Boson Sampling
• Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
• Classical simulation of lossy boson sampling using matrix product operators
• Dynamical phase transitions in sampling complexity
• Benchmarking of Gaussian boson sampling using two-point correlators
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• A limit formula for the quantum fidelity
• An efficient tree decomposition method for permanents and mixed discriminants
• The complexity of simulating constant-depth BosonSampling
• Entanglement formation in continuous-variable random quantum networks
• Boson Sampling is Robust to Small Errors in the Network Matrix

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