Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

Understand

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.