Approximating unitaries with elements from a t-design

Question

(This is basically a reference request)

I am wondering if there are any results out there on to what accuracy a given unitary can be approximated with an element drawn from a t-design.

To elaborate a bit, consider the Haar measure over $U(d)$. This integrates over all the unitaries in $U(d)$. So we could say that given some fixed unitary $U_0$, there is an element in the set of unitaries integrated over by the Haar measure which approximates $U_0$ well (this is trivial of course, since $U_0$ itself occurs in the integration).

Now consider a $t$-design. The $t$-design is a finite set of unitaries which has some special properties - namely summing over that set approximates doing a Haar integral. Heuristically, the set of unitaries in the $t$-design looks like the full set of unitaries. So now given some specific unitary $U_0\in U(d)$, is it the case that some element of the $t$-design must be close to $U_0$?

Answer 1

It’s straightforward to see that a random element $U$ drawn from a design is, with very high probability, far away from any fixed unitary $V$, i.e. you can show that the distance between $U$ and $V$ (in operator norm or in the diamond norm of their channels) is on average very close to maximal.

But what you’re asking about is if there exists at least one element in the design which is close to some fixed unitary $V$. Without knowing anything else about the structure of the design, you’re asking when do unitary $t$-designs cover the unitary group (i.e. every $U$ in $U(d)$ is at most $\epsilon$ away, in some norm, from some element of the design. Equivalently, putting $\epsilon$-balls around each unitary, $U(d)$ is contained in the union of the balls.)

This doesn't address your question rigorously, but here's an argument for why the design order should be at least $t=O(d^2)$, in order for $t$-designs to cover $U(d)$. For an exact unitary $t$-design $\mathcal{E}$, a lower bound on the cardinality is $|\mathcal{E}| \geq d^{2t}/t!$. If the number of elements in $\mathcal{E}$ is some constant multiple of this lower bound, then we find that $|\mathcal{E}|$ becomes comparable to the volume of the unitary group (more precisely, the vol($U(d)$)/vol($\epsilon$-ball)) when $t\sim d^2$. But to rigorously show that for some $t$, unitary $t$-designs cover the unitary group will require more work.