Random quantum circuits anti-concentrate in log depth

Understand

We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes.

• Understanding the conditions for anti-concentration is important for determining which quantum circuits are difficult to simulate classically, as anti-concentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation.
• Our definition of anti-concentration is that the expected collision probability, that is, the probability that two independently drawn outcomes will agree, is only a constant factor larger than if the distribution were uniform.
• We show that when the 2-local gates are each drawn from the Haar measure (or any two-design), at least $\Omega(n \log(n))$ gates (and thus $\Omega(\log(n))$ circuit depth) are needed for this condition to be met on an $n$ qudit circuit.