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 n depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in poly n depth, and in all-to-all-connected circuits in poly 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 n-sized or poly 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 unitary ensembles conjectured to form PRUs. 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.