Yuzhen Zhang, Sagar Vijay, Yingfei Gu, Yimu Bao (Jul 04 2025).
Abstract: 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.