We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least inverse exponential in depth, on any output qubit touched by its lightcone. Our result on scrambling speed works with high probability over the choice of a circuit from an ensemble, as opposed to just working in expectation. As an application, we give the first polynomial-time algorithm for learning log-depth random quantum circuits with Haar random gates up to polynomially small diamond distance, given oracle access to the circuit. Other applications of this new scrambling speed lower bound include: $\bullet$ An optimal $Ω(\log \varepsilon^{-1})$ depth lower bound for $\varepsilon$-approximate unitary designs on any circuit architecture; $\bullet$ A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit. Our learning and depth-testing algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties.

翻译：我们证明了酉哈测度的一种Carbery-Wright风格的反集中不等式，通过证明随机酉矩阵条目中多项式落入ε范围内的概率至多为ε的多项式。利用该结果，我们证明了随机量子电路的置乱速度存在下界：即每个输入量子比特对其光锥所触及的任何输出量子比特的影响至少为深度的指数倒数。我们的置乱速度结果以高概率适用于从系综中选取的电路，而不仅仅是期望意义上的结果。作为应用，我们首次给出了在多项式小的钻石距离下学习具有哈随机门的对数深度随机量子电路的多项式时间算法，前提是能够通过预言机访问该电路。这一新的置乱速度下界的其他应用包括：• 对于任何电路架构上ε近似酉设计的最优Ω(log ε⁻¹)深度下界；• 一种多项式时间量子算法，在给定电路预言机访问权限的情况下，能够计算有界深度电路的深度。我们的学习和深度测试算法适用于任何几何维度定义的架构，并且可以推广到具有良好光锥性质的一类广泛架构。