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

Abstract

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 \ge x\right)\le 2D_t\frac{e^{-|\mathcal{S}|x\mathrm{arctanh}(x)}}{(1-x^2{)}^{|\mathcal{S}|/2}}=O\left(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}(t\log (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.

36 pages, 6 figures, some typos fixed and other minor changes

References in corpus (6)

• Surface codes: Towards practical large-scale quantum computation
• The mother of all protocols: Restructuring quantum information's family tree
• Linear growth of quantum circuit complexity
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• How to check universality of quantum gates?
• Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm

Cited by in corpus (1)

• Linear programming with unitary-equivariant constraints