The field of quantum computation heavily relies on the belief that quantum computation violates the extended Church Turing thesis, namely, that quantum many-body systems cannot be simulated by classical ones with only polynomial overhead. Importantly, we must ask: what experimental evidence do we have for this bold assumption? A major effort towards providing such evidence had concentrated on random quantum circuit sampling (RCS) as in the famous supremacy experiment by Google from 2019. I will describe a recent work with Gao, Landau, Liu and Vazirani in which we give a polynomial time classical algorithm for simulating such RCS experiments. Our algorithm gives strong evidence that RCS cannot be the basis for near term experimental evidence for scalable exponential quantum advantage.
[mehr]
