A polynomial-time classical algorithm for noisy random circuit sampling

DOI10.1145/3564246.3585234MaRDI QIDQ6499276zbMATH OpenWikidataFDO

Authors Dorit Aharonov, Xun Gao, Zeph A. Landau, Yunchao Liu, Umesh V. Vazirani

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585234

zbMATH Keywords

quantum supremacyrandom circuit sampling

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Complexity-theoretic foundations of quantum supremacy experiments
• Entanglement and correlation functions of the quantum Motzkin spin-chain
• On the classical hardness of spoofing linear cross-entropy benchmarking
• Quantum Complexity Theory
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Random quantum circuits are approximate 2-designs
• The computational complexity of linear optics
• Upper bounds on the noise threshold for fault-tolerant quantum computing

Cited in

(5)

• Efficient reconstruction, benchmarking and validation of cross-talk models in readout noise in near-term quantum devices
• The computational advantage of MIP* vanishes in the presence of noise
• The computational advantage of MIP* vanishes in the presence of noise
• A qubit, a coin, and an advice string walk into a relational problem
• Analysis of quantum primitives for quantum utility

This page was built for publication: A polynomial-time classical algorithm for noisy random circuit sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499276)