Computational advantage of quantum random sampling
The theoretical underpinning of quantum random sampling in terms of computational complexity and verifiability, as well as the practical aspects of its experimental implementation using superconducting and photonic devices and its classical simulation are reviewed.
Abstract
Quantum computers have improved and recent experiments have claimed quantum advantage -- completion of a computational task that is evidently hard for any conventional computer. The problem solved is that of obtaining samples, by quantum measurement, from a certain probability distribution. This review shows in what precise way quantum random sampling can be seen as a computation. It explains what that computation solves, in what way it outperforms classical computations, and what methods of verification are available. Quantum random sampling becomes a first test of the presumed exponential computational advantage of quantum computers over classical ones.