Exact simulation of Gaussian boson sampling in polynomial space and exponential time
Nicolás Quesada, Juan Miguel Arrazola
Abstract
This work introduces a classical algorithm that can simulate the output of a Gaussian Boson Sampling device in time exponential in the number of photons detected and in only polynomial space in the number of modes/photons. The algorithm takes advantage of the fact that the marginal Wigner functions of Gaussian states can be easily calculated.
Topics & Concepts
GaussianTime complexitySampling (signal processing)AlgorithmPolynomialExponential functionMathematicsBenchmark (surveying)Computer scienceDiscrete mathematicsDetectorPhysicsQuantum mechanicsMathematical analysisGeodesyGeographyTelecommunicationsNeural Networks and Reservoir ComputingQuantum Information and CryptographyQuantum Computing Algorithms and Architecture