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 / ε ) ) + 2 O ( k log  k ) in one dimension and O ( log  log  ( N / ε ) ) + 2 O ( k log  k ) 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 ( 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.