# Aproximating unitaries with elements from a t-design

(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$$?

• I guess what you’re specifically after is how the closeness (by some measure) improves with the $t$ of the $t$-design, if at all? Since the Pauli matrices are a 1-design, they can be a really bad approximation but, heuristically, you expect a larger set of unitaries as t increases, and hence the approximation improves. Mar 6 '20 at 6:24
• @DaftWullie, yes thats right. I'm also interested in if that closeness measure depends on just $t$, or also on the dimension. Mar 6 '20 at 17:57
• Why are you interested in that? Mar 7 '20 at 22:32
• @NorbertSchuch, I noticed the paper arxiv.org/pdf/2002.09524.pdf, which shows you can do t-designs with a number of non-Clifford gates that doesn't scale with the number of qubits, and am wondering if there are implications for how many non-Clifford gates are really needed to perform arbitrary unitaries. Mar 17 '20 at 18:20
• (I just realised that this question is 1.5y old, I hope you don't mind) As we comment in that paper, you can argue that the "complexity" of designs increase with its order, so in particular our construction shows that it increases with the number of non-Clifford gates. This is based on the idea of arxiv.org/abs/1912.04297. On the other hand, if you're really interested how well you can approximate any unitary, you should look at $\varepsilon$-nets. arxiv.org/abs/2007.10885 shows that you need order $t\sim d^{5/2}\varepsilon^{-1}$ to achieve this. Oct 22 at 7:39

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.