A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Yunchao Liu (UC Berkeley)
https://simons.berkeley.edu/events/qu...
Quantum Colloquium
Quantum random circuit sampling (RCS) is a basic primitive at the heart of recent "quantum supremacy" experiments. These experiments can be modeled as sampling from a random quantum circuit where each gate is subject to a small amount of noise. In this talk we give an overview of RCS and discuss recent progress on understanding its computational complexity.
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. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments.
Based on joint work with Dorit Aharonov, Xun Gao, Zeph Landau and Umesh Vazirani, arxiv: 2211.03999
Panel featuring Adam Bouland (Stanford), Scott Aaronson (UT Austin), and Sergio Boixo (Google); Umesh Vazirani (UC Berkeley; moderator).
Watch video A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling online without registration, duration hours minute second in high quality. This video was added by user Simons Institute 01 January 1970, don't forget to share it with your friends and acquaintances, it has been viewed on our site 2,57 once and liked it 4 people.