A Random Matrix Model for Random Approximate t-Designs

Abstract

For a Haar random set$\mathcal {S}\subset U(d)$of quantum gates we consider the uniform measure$\nu_{\mathcal {S}}$whose support is given by$\mathcal {S}$. The measure$\nu _{\mathcal {S}}$can be regarded as a$\delta (\nu _{\mathcal {S}},t)$-approximate$t$-design,$t\in \mathbb {Z}_{+}$. We propose a random matrix model that aims to describe the probability distribution of$\delta (\nu _{\mathcal {S}},t)$for any$t$. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined by$t$. We prove that, the operator norm of this matrix,$\delta ({t})$, is the random variable to which$\sqrt {|\mathcal {S}|}\delta (\nu _{\mathcal {S}},t)$converges in distribution when the number of elements in$\mathcal {S}$grows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilities$\mathbb {P}(\delta (t)>2+\epsilon)$, for any$\epsilon >0$. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability 1 there is$t\in \mathbb {Z}_{+}$such that$\sup _{k\in \mathbb {Z}_{+}}\delta (k)=\delta (t)$. Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality of$\mathcal {S}$. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilities$\mathbb {P}(\sqrt {\mathcal {S}}\delta (\nu _{\mathcal {S}},t)>2+\epsilon)$are bounded from above by the tail probabilities$\mathbb {P}(\delta (t)>2+\epsilon)$of our random matrix model. In particular our conjecture implies that a Haar random set$\mathcal {S}\subset U(d)$satisfies the spectral gap conjecture with the probability 1.