Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time

Abstract

We introduce an exact classical algorithm for simulating Gaussian Boson Sampling (GBS). The complexity of the algorithm is exponential in the number of photons detected, which is itself a random variable. For a fixed number of modes, the complexity is in fact equivalent to that of calculating output probabilities, up to constant prefactors. The simulation algorithm can be extended to other models such as GBS with threshold detectors, GBS with displacements, and sampling linear combinations of Gaussian states. In the specific case of encoding non-negative matrices into a GBS device, our method leads to an approximate sampling algorithm with polynomial runtime. We implement the algorithm, making the code publicly available as part of Xanadu's The Walrus library, and benchmark its performance on GBS with random Haar interferometers and with encoded Erdős-Renyi graphs.

arXiv commentThe algorithms presented in this paper can be accessed using The Walrus library available at https://github.com/XanaduAI/thewalrus

References in corpus (27)

• Gaussian Quantum Information
• Boson Sampling on a Photonic Chip
• Experimental Boson Sampling
• Photonic Boson Sampling in a Tunable Circuit
• Gaussian Boson Sampling
• Boson Sampling for Molecular Vibronic Spectra
• Boson Sampling from Gaussian States
• Experimental Scattershot Boson Sampling
• Noise-free high-efficiency photon-number-resolving detectors
• Generation and sampling of quantum states of light in a silicon chip
• A detailed study of Gaussian Boson Sampling
• No imminent quantum supremacy by boson sampling
• Using Gaussian Boson Sampling to Find Dense Subgraphs
• Gaussian Boson Sampling using threshold detectors
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
• Experimental Gaussian Boson Sampling
• Simulating realistic non-Gaussian state preparation
• Simple factorization of unitary transformations
• Quantum approximate optimization with Gaussian boson sampling
• Boson sampling with Gaussian measurements
• Point Processes with Gaussian Boson Sampling
• Franck-Condon factors by counting perfect matchings of graphs with loops
• Approximating Vibronic Spectroscopy with Imperfect Quantum Optics
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Driven Boson Sampling
• Hafnians, perfect matchings and Gaussian matrices
• Exact Boson Sampling using Gaussian continuous variable measurements

Cited by in corpus (32)

• Quantum computational advantage using photons
• Computational advantage of quantum random sampling
• Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Beyond photon pairs: Nonlinear quantum photonics in the high-gain regime
• Scalable and Programmable Phononic Network with Trapped Ions
• The Complexity of Bipartite Gaussian Boson Sampling
• Classical simulation of boson sampling based on graph structure
• Fast simulation of bosonic qubits via Gaussian functions in phase space
• Quantum Algorithm for Simulating Molecular Vibrational Excitations
• Simulating complex networks in phase space: Gaussian boson sampling
• Simulating lossy Gaussian boson sampling with matrix product operators
• Degenerate Squeezing in Waveguides: A Unified Theoretical Approach
• Efficient computation of permanents, with applications to boson sampling and random matrices
• Classical models may be a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model
• Experimental demonstration of Gaussian boson sampling with displacement
• Quantum-inspired classical algorithm for molecular vibronic spectra
• Certification of Gaussian Boson Sampling via graph theory
• Simulating macroscopic quantum correlations in linear networks
• Piquasso: A Photonic Quantum Computer Simulation Software Platform
• Continuous Variable Quantum Algorithms: an Introduction
• Gaussian boson sampling and multi-particle event optimization by machine learning in the quantum phase space
• Efficient approximation of experimental Gaussian boson sampling
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone
• Validation of a noisy Gaussian boson sampler via graph theory
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• On the learning abilities of photonic continuous-variable Born machines
• Speedup in Classical Simulation of Gaussian Boson Sampling
• Realistic photon-number resolution in Gaussian boson sampling
• Optical Quantum Computing
• Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond