Computational advantage of quantum random sampling

Abstract

Quantum random sampling is the leading proposal for demonstrating a computational advantage of quantum computers over classical computers. Recently the first large-scale implementations of quantum random sampling have arguably surpassed the boundary of what can be simulated on existing classical hardware. Here the theoretical underpinning of quantum random sampling is comprehensively reviewed in terms of computational complexity and verifiability, as are the practical aspects of its experimental implementation using superconducting and photonic devices and its classical simulation. Open questions in the field are discussed, and perspectives for the road ahead, including potential applications of quantum random sampling, are provided.