Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution
Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution
复制标题
DOI：
10.1103/prxquantum.3.040329
复制
发表时间：
2021-12
期刊：
影响因子：
9.7
通讯作者：
A. Deshpande;Pradeep Niroula;O. Shtanko;A. Gorshkov;Bill Fefferman;M. Gullans
中科院分区：
文献类型：
--
作者：
A. Deshpande;Pradeep Niroula;O. Shtanko;A. Gorshkov;Bill Fefferman;M. Gullans
本文研究了噪声随机电路的输出分布特性。我们得到的输出分布的预期距离的上限和下限的“无用的”均匀分布。这些界限是紧密的电路深度的依赖关系。我们的证明技术也使我们能够对有噪声和无噪声电路是否存在反集中做出陈述。我们发现了一些有趣的后果，旨在显示量子计算的优势，超过经典计算的采样方案的硬度证明。具体来说，我们讨论了最近的障碍结果的深度不可知和/或噪声不可知的证明技术。我们表明，在一定的深度制度，噪声不可知的证明技术可能仍然工作，以证明在文献中的量子计算优势的一个常见的索赔，相反的是什么被认为在这项工作之前。
We study the properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the"useless"uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work.