Computational advantage of quantum random sampling

2022/06/08 by Dominik Hangleiter, Jens Eisert · 1 voice · 2 citations
Physics and Astronomy · Computer Science · #quant-ph #cond-mat.quant-gas #cs.CC

paper · pdf · doi:10.1103/revmodphys.95.035001

arxiv published 2022/06/08 · arxiv updated 2023/03/10

Abstract

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.

Cited by

• Qudit extension of parameterized IQP circuits: A generative quantum machine learning approach to integer data
• Theory of the Matchgate Commutant

Discussions

• Computational advantage of quantum random sampling [hn, 1 points, 0 comments]

Related

• Can Quantum Computing Improve Uniform Random Sampling of Large Configuration Spaces? (Preprint)
• Race for Quantum Advantage using Random Circuit Sampling
• Anticoncentrated n-bit distribution from log(n) qubits
• Classical Sampling of Random Quantum Circuits with Bounded Fidelity
• Monte Carlo simulation of random circuit sampling in quantum computing