Designs from magic-augmented Clifford circuits

We introduce magic-augmented Clifford circuits -- architectures in which Clifford circuits are preceded and/or followed by constant-depth circuits of non-Clifford ("magic") gates -- as a resource-efficient way to realize approximate k-designs, with reduced circuit depth and usage of magic. We prove that shallow Clifford circuits, when augmented with constant-depth circuits of magic gates, can generate approximate unitary and state k-designs with relative error. The total circuit depth for these constructions on N qubits is O(log (N/eps)) +2^{O(k log k)} in one dimension and O(log log(N/eps))+2^{O(k log k)} in all-to-all circuits using ancillas, which improves upon previous results for small k>3. Furthermore, our construction of relative-error state k-designs only involves states with strictly local magic. The required number of magic gates is parametrically reduced when considering k-designs with bounded additive error. As an example, we show that shallow Clifford circuits followed by O(k^2) single-qubit magic gates, independent of system size, can generate an additive-error state k-design. We develop a classical statistical mechanics description of our random circuit architectures, which provides a quantitative understanding of the required depth and number of magic gates for additive-error state k-designs. We also prove no-go theorems for various architectures to generate designs with bounded relative error.