Matrix concentration inequalities and efficiency of random universal sets of quantum gates

Quantum 7, 983 (2023).

https://doi.org/10.22331/q-2023-04-20-983

For a random set $mathcal{S} subset U(d)$ of quantum gates we provide bounds on the probability that $mathcal{S}$ forms a $delta$-approximate $t$-design. In particular we have found that for $mathcal{S}$ drawn from an exact $t$-design the probability that it forms a $delta$-approximate $t$-design satisfies the inequality $mathbb{P}left(delta geq x right)leq 2D_t , frac{e^{-|mathcal{S}| x , mathrm{arctanh}(x)}}{(1-x^2)^{|mathcal{S}|/2}} = Oleft( 2D_t left( frac{e^{-x^2}}{sqrt{1-x^2}} right)^{|mathcal{S}|} right)$, where $D_t$ is a sum over dimensions of unique irreducible representations appearing in the decomposition of $U mapsto U^{otimes t}otimes bar{U}^{otimes t}$. We use our results to show that to obtain a $delta$-approximate $t$-design with probability $P$ one needs $O( delta^{-2}(tlog(d)-log(1-P)))$ many random gates. We also analyze how $delta$ concentrates around its expected value $mathbb{E}delta$ for random $mathcal{S}$. Our results are valid for both symmetric and non-symmetric sets of gates.