  We prove that local random quantum circuits acting on n qubits composed of
O(t^{10} n^2) many nearest neighbor two-qubit gates form an approximate unitary
t-design. Previously it was unknown whether random quantum circuits were a
t-design for any t > 3.
  The proof is based on an interplay of techniques from quantum many-body
theory, representation theory, and the theory of Markov chains. In particular
we employ a result of Nachtergaele for lower bounding the spectral gap of
frustration-free quantum local Hamiltonians; a quasi-orthogonality property of
permutation matrices; a result of Oliveira which extends to the unitary group
the path-coupling method for bounding the mixing time of random walks; and a
result of Bourgain and Gamburd showing that dense subgroups of the special
unitary group, composed of elements with algebraic entries, are infty-copy
tensor-product expanders.
  We also consider pseudo-randomness properties of local random quantum
circuits of small depth and prove that circuits of depth O(t^{10}n) constitute
a quantum t-copy tensor-product expander. The proof also rests on techniques
from quantum many-body theory, in particular on the detectability lemma of
Aharonov, Arad, Landau, and Vazirani.
  We give applications of the results to cryptography, equilibration of closed
quantum dynamics, and the generation of topological order. In particular we
show the following pseudo-randomness property of generic quantum circuits:
Almost every circuit U of size O(n^k) on n qubits cannot be distinguished from
a Haar uniform unitary by circuits of size O(n^{(k-9)/11}) that are given
oracle access to U.
