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 toward 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 2 ) , 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 toward state k -designs. Second, we derive tight bounds on the convergence of t -doped Clifford circuits toward relative-error k -designs, showing that t = Θ ~ ( n k ) is both necessary and sufficient for the ensemble to form a relative ε -approximate k -design. Similarly, t = Θ ~ ( n ) is required to generate pseudorandom 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 analyze high-order 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.