Efficient approximation of experimental Gaussian boson sampling
arXiv:2109.11525
Abstract
Two recent landmark experiments have performed Gaussian boson sampling (GBS) with a non-programmable linear interferometer and threshold detectors on up to 144 output modes (see Refs.~\onlinecite{zhong_quantum_2020,zhong2021phase}). Here we give classical sampling algorithms with better total variation distance and Kullback-Leibler divergence than these experiments and a computational cost quadratic in the number of modes. Our method samples from a distribution that approximates the single-mode and two-mode ideal marginals of the given Gaussian boson sampler, which are calculated efficiently. One implementation sets the parameters of a Boltzmann machine from the calculated marginals using a mean field solution. This is a 2nd order approximation, with the uniform and thermal approximations corresponding to the 0th and 1st order, respectively. The th order approximation reproduces Ursell functions (also known as connected correlations) up to order with a cost exponential in and high precision, while the experiment exhibits higher order Ursell functions with lower precision. This methodology, like other polynomial approximations introduced previously, does not apply to random circuit sampling because the th order approximation would simply result in the uniform distribution, in contrast to GBS.
Improved analysis on the estimation of total variation distance difference with a finite number of samples. Provided evidence for the stability of the KL divergence difference with a finite number of samples. Changed the term "correlation" to "Ursell function", for clarity. 17 pages, 11 figures
References in corpus (43)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Gaussian Quantum Information
- Characterizing Quantum Supremacy in Near-Term Devices
- Strong quantum computational advantage using a superconducting quantum processor
- Gaussian Boson Sampling
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Average-case complexity versus approximate simulation of commuting quantum computations
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- 0.5 Petabyte Simulation of a 45-Qubit Quantum Circuit
- A detailed study of Gaussian Boson Sampling
- A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
- Efficient classical simulation of random shallow 2D quantum circuits
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- 64-Qubit Quantum Circuit Simulation
- Gaussian Boson Sampling using threshold detectors
- Massively parallel quantum computer simulator, eleven years later
- Efficient algorithm for boson sampling with partially distinguishable photons
- Efficient classical simulation of noisy random quantum circuits in one dimension
- The Boundary for Quantum Advantage in Gaussian Boson Sampling
- Regimes of classical simulability for noisy Gaussian boson sampling
- Classical Simulation of Quantum Supremacy Circuits
- Simulation of low-depth quantum circuits as complex undirected graphical models
- Experimental Gaussian Boson Sampling
- Classical Simulation of Intermediate-Size Quantum Circuits
- Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
- Quantum Supremacy Is Both Closer and Farther than It Appears
- Simulating the Sycamore quantum supremacy circuits
- Noise and the frontier of quantum supremacy
- Gaussian Noise Sensitivity and BosonSampling
- Benchmarking of Gaussian boson sampling using two-point correlators
- Simulating complex networks in phase space: Gaussian boson sampling
- Simulability of Imperfect Gaussian and Superposition Boson Sampling
- Quantum Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits
- Classical simulability of noisy boson sampling
- Quantum supremacy and random circuits
- Benchmarking near-term quantum computers via random circuit sampling
- Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer
- Quantum Supremacy Circuit Simulation on Sunway TaihuLight
- Fourier analysis of sampling from noisy chaotic quantum circuits
- Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight
- Sample-efficient benchmarking of multi-photon interference on a boson sampler in the sparse regime
- Marginal probabilities in boson samplers with arbitrary input states