The non-Clifford cost of random unitaries

Recent years have enjoyed a strong interest in exploring properties and applications of random quantum circuits. In this work, we explore the ensemble of t-doped Clifford circuits on n qubits, consisting of Clifford circuits interspersed with t single-qubit non-Clifford gates. We establish rigorous convergence bounds towards unitary k-designs, revealing the intrinsic cost in terms of non-Clifford resources in various flavors. First, we analyze the k-th order frame potential, which quantifies how well the ensemble of doped Clifford circuits is spread within the unitary group. We prove that a quadratic doping level, t = (k²), is both necessary and sufficient to approximate the frame potential of the full unitary group. As a consequence, we refine existing upper bounds on the convergence of the ensemble towards state k-designs. Second, we derive tight bounds on the convergence of t-doped Clifford circuits towards relative-error k-designs, showing that t = (nk) is both necessary and sufficient for the ensemble to form a relative -approximate k-design. Similarly, t = (n) is required to generate pseudo-random unitaries. All these results highlight that generating random unitaries is extremely costly in terms of non-Clifford resources, and that such ensembles fundamentally lie beyond the classical simulability barrier. Additionally, we introduce doped-Clifford Weingarten functions to derive analytic expressions for the twirling operator over the ensemble of random doped Clifford circuits, and we establish their asymptotic behavior in relevant regimes.