Boson Sampling Gaussian Boson Sampling

Short answer: Boson sampling is a model of photonic quantum computing designed to show that a limited, non-universal quantum device can do something classical computers cannot do efficiently. Gaussian boson sampling (GBS) is a variant that uses squeezed light. Experiments have claimed to be hard to simulate classically, but papers from 2020 to 2024 give faster classical simulation algorithms, and a 2024 Nature Physics paper argues a classical method can simulate the largest experiment so far, which it says calls the quantum advantage claims into question. The debate is active and the claims are the authors' own.

What boson sampling is

A 2020 Physical Review Research paper describes boson sampling as a model of photonic quantum computing introduced to argue that non-universal photonic quantum computers cannot be efficiently simulated classically. Gaussian boson sampling emerged as a paradigm that addresses some challenges in scaling. Instead of indistinguishable single photons, GBS prepares a multimode Gaussian state, typically by sending squeezed light through a linear-optical interferometer, and measures it with photon detectors.

A 2022 PRX Quantum paper adds that GBS has been proposed to argue that a rudimentary non-universal quantum computer can perform computations beyond the reach of any present or future classical supercomputer, and that building a sufficiently large Gaussian boson sampler would refute the extended Church-Turing thesis. It says there is complexity-theoretic evidence that GBS is hard to simulate classically, because of the difficulty of calculating the probability amplitude of a single outcome for a pure Gaussian state. To be confident a classical computer will never outperform the device, it is important to find the best classical algorithm.

Better classical algorithms

The 2020 paper introduces an exact classical algorithm for simulating GBS whose complexity is exponential in the number of photons detected, and equivalent to calculating output probabilities for a fixed number of modes. It extends to variants such as threshold detectors and displacements. For the case of encoding non-negative matrices, it gives an approximate algorithm with polynomial runtime. The authors implemented and benchmarked it in a publicly available library.

The 2022 paper presents an algorithm quadratically faster than earlier methods. Its complexity is exponential in the number of photon pairs detected, not photons, and is proportional to the time for a pure-state probability amplitude. It uses auxiliary conditioning variables to reduce sampling to computing pure-state amplitudes, whose dominant step is a loop hafnian. The authors report computing pure-state probabilities for events with up to 50 photons on a single workstation, without a supercomputer.

Noise changes the picture

The 2024 Nature Physics paper says that while noiseless GBS is believed hard to simulate classically, current experiments suffer from high photon loss and other noise, and are nevertheless claimed to be hard to simulate. The authors present a classical tensor-network algorithm whose complexity can be significantly reduced when the photon loss rate is high. They say it simulates the largest GBS experiment so far with relatively modest computational resources, and they exhibit evidence that their classical sampler can simulate the ideal distribution better than the experiment can. They say this calls into question the claims of experimental quantum advantage.

What this does not tell you

These papers do not show that GBS can never give an advantage. They concern noisy experiments and specific classical methods, and the 2024 authors present their evidence as calling the claims into question, not as settling them. Better experiments with less loss could change the conclusion.

FAQ

What is Gaussian boson sampling?

A photonic sampling task using squeezed light sent through an interferometer and measured with photon detectors.

Why was it proposed?

To argue that a limited quantum device can do something classical computers cannot do efficiently.

Have classical computers caught up?

A 2024 paper claims a classical algorithm can simulate the largest experiment so far, which it says questions the advantage claims.

Does noise matter?

Yes. High photon loss makes the experiment easier to simulate classically in that paper's method.

Is the question settled?

No. The papers describe an ongoing contest between experiments and classical algorithms.