A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh Vazirani
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.
Topics & Concepts
AlgorithmPolynomialSampling (signal processing)Time complexityInverseNoise (video)Constant (computer programming)TuringComputer scienceMathematicsApplied mathematicsMathematical analysisTelecommunicationsArtificial intelligenceGeometryDetectorProgramming languageImage (mathematics)Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyComputability, Logic, AI Algorithms