Quantum random sampling is the leading proposal for demonstrating a computational advantage of quantum computers over classical computers. Recently, first large-scale implementations of quantum random sampling have arguably surpassed the boundary of what can be simulated on existing classical hardware. In this article, we comprehensively review 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. We discuss in detail open questions in the field and provide perspectives for the road ahead, including potential applications of quantum random sampling.

翻译：量子随机抽样是证明量子计算机在计算上优于古典计算机的主要建议。最近,首次大规模实施量子随机抽样可能已经超出了现有古典硬件所模拟的界限。在本篇文章中,我们从计算复杂性和可核查性的角度全面审查量子随机抽样的理论基础,以及利用超导和光化设备及其古典模拟试验实施的实际方面。我们详细讨论了实地的开放问题,并为今后的道路提供了前景,包括量子随机抽样的可能应用。