Abstract
For a random set S ⊂ U(d) of quantum gates we provide bounds on the probability that S forms a δ-approximate t-design. In particular we have found that for S drawn from an exact t-design the probability that it forms a δ-approximate t-design satisfies the inequality P(δ ≥ x )≤ 2D_t e^-|S| x arctanh(x)/(1-x²)^|S|/2 = O( 2D_t ( e^-x²/√1-x² )^|S| ), where D_t is a sum over dimensions of unique irreducible representations appearing in the decomposition of U ↦ U^⊗ t⊗ U^⊗ t. We use our results to show that to obtain a δ-approximate t-design with probability P one needs O( δ⁻²(tlog(d)-log(1-P))) many random gates. We also analyze how δ concentrates around its expected value Eδ for random S. Our results are valid for both symmetric and non-symmetric sets of gates.