  Decoupling has become a central concept in quantum information theory with
applications including proving coding theorems, randomness extraction and the
study of conditions for reaching thermal equilibrium. However, our
understanding of the dynamics that lead to decoupling is limited. In fact, the
only families of transformations that are known to lead to decoupling are
(approximate) unitary two-designs, i.e., measures over the unitary group which
behave like the Haar measure as far as the first two moments are concerned.
Such families include for example random quantum circuits with O(n^2) gates,
where n is the number of qubits in the system under consideration. In fact, all
known constructions of decoupling circuits use \Omega(n^2) gates.
  Here, we prove that random quantum circuits with O(n log^2 n) gates satisfy
an essentially optimal decoupling theorem. In addition, these circuits can be
implemented in depth O(log^3 n). This proves that decoupling can happen in a
time that scales polylogarithmically in the number of particles in the system,
provided all the particles are allowed to interact. Our proof does not proceed
by showing that such circuits are approximate two-designs in the usual sense,
but rather we directly analyze the decoupling property.
