Total: 1
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/ϵ))+2O(klogk) in one dimension and O(loglog(N/ϵ))+2O(klogk) in all-to-all circuits using ancillas, which improves upon previous results for small k≥4. 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(k2) 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.