Berkeley computer theorists show path to verifying that quantum beats classical

UC Berkeley computer theorists led by CS Prof. Umesh Vazirani,  published a proof of random circuit sampling (RCS) as a verification method to prove quantum supremacy in a paper published Monday, Oct. 29, in the journal Nature Physics.  Quantum supremacy is the term that describes a quantum computer’s ability to solve a computational task that would be prohibitively difficult for any classical algorithm.  “Besides being a milestone on the way to useful quantum computers, quantum supremacy is a new kind of physics experiment to test quantum mechanics in a new regime. The basic question that must be answered for any such experiment is how confident can we be that the observed behavior is truly quantum and could not have been replicated by classical means. That is what our results address,” said Vazirani.