Random unitaries in extremely low depth

We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over n qubits in log n depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in poly\(log n\) depth, and in all-to-all-connected circuits in poly\(log log n\) depth. In all three cases, the n dependence is optimal and improves exponentially over known results. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Our construction glues local random unitaries on log n-sized or poly\(log n\)-sized patches of qubits to form a global random unitary on all n qubits. In the case of designs, the local unitaries are drawn from existing constructions of approximate unitary k-designs, and hence also inherit an optimal scaling in k. In the case of PRUs, the local unitaries are drawn from existing PRU constructions. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.