Quadratic speedup for simulating Gaussian boson sampling

We introduce an algorithm for the classical simulation of Gaussian boson sampling that is quadratically faster than previously known methods. The complexity of the algorithm is exponential in the number of photon pairs detected, not the number of photons, and is directly proportional to the time req...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-08
Main Authors: Quesada, Nicolás, Chadwick, Rachel S, Bell, Bryn A, Juan Miguel Arrazola, Vincent, Trevor, Qi, Haoyu, García-Patrón, Raúl
Format: Article
Language:English
Subjects:
Algorithms
Amplitudes
Mathematical analysis
Normal distribution
Photons
Probability
Sampling
Workstations
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce an algorithm for the classical simulation of Gaussian boson sampling that is quadratically faster than previously known methods. The complexity of the algorithm is exponential in the number of photon pairs detected, not the number of photons, and is directly proportional to the time required to calculate a probability amplitude for a pure Gaussian state. The main innovation is to use auxiliary conditioning variables to reduce the problem of sampling to computing pure-state probability amplitudes, for which the most computationally-expensive step is calculating a loop hafnian. We implement and benchmark an improved loop hafnian algorithm and show that it can be used to compute pure-state probabilities, the dominant step in the sampling algorithm, of up to 50-photon events in a single workstation, i.e., without the need of a supercomputer.
ISSN:2331-8422