← Back to papers
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
D. Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, U. Vazirani·November 8, 2022·DOI: 10.1145/3564246.3585234
PhysicsComputer Science
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. The algorithm is based on a quantum analog of noise induced low degree approximations of Boolean functions, which takes the form of the truncation of a Feynman path integral in the Pauli basis.