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 kth 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=Θ[over ~](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=Θ[over ~](nk) is both necessary and sufficient for the ensemble to form a relative ε-approximate k-design. Similarly, t=Θ[over ~](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.