论文标题
用于嘈杂随机电路采样的多项式经典算法
A polynomial-time classical algorithm for noisy random circuit sampling
论文作者
论文摘要
我们给出了一种多项式时间古典算法，用于从抗浓缩的噪声随机量子电路的输出分布到反向多项式总变化距离内的取样。这提供了有力的证据表明，在每个门闸的存在恒定的噪声速率的情况下，随机电路采样（RCS）不能成为对扩展教会培养论文的可扩展实验违规的基础。我们的算法在当前形式不实用，也不解决有限大小的基于RCS的量子至上实验实验。
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.
