A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling

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.

Authors

• Dorit Aharonov
• Xun Gao
• Zeph Landau
• Yunchao Liu 0002
• Umesh V. Vazirani

Keywords

• Quantum supremacy
• Random circuit sampling