## 12.5 Approximating generic unitaries is hard, but…

Now that we understand approximations of unitary operators, we can revisit the question of universality that we touched upon in Sections 2.13 and 3.5.
Recall that we call a finite set **universal** if *any* *arbitrary accuracy* by some unitary constructed using only gates from **elementary**).
In other words,

For example, each of the following sets of gates is universal:

\{H,\texttt{c-}S\} \{H,T,\texttt{c-NOT}\} \{H,S,\texttt{Toff}\}

where *controlled*

But now we can be a bit more precise with the question that the notion of universality is trying to answer: given a universal set of gates, how hard is it to approximate any desired unitary transformation with accuracy *how many gates do we need*?

The answer is *a lot*.
In fact, it is exponential in the number of qubits — most unitary transformation require large quantum circuits of elementary gates.
We can show this by a counting argument (along with a healthy dose of geometric intuition).

Consider a universal set of gates ^{245} for the first gate, since there are *polynomial* in *the scaling is exponential in n but only logarithmic in 1/\varepsilon*.

When we add qubits, the space of possible unitary operations grows very rapidly, and we have to work exponentially hard if we want to approximate the resulting unitaries with some prescribed precision. If, however, we fix the number of qubits and instead ask for better and better approximations, then things are much easier, since we only have to work logarithmically hard.

The snag is that this counting argument does not give us any hints as to how we can actually build such approximations. A more constructive approach is to pick a set of universal gates and play with them, building more and more complex circuits. There is an important theorem in this direction that tells us that it does not matter much which particular universal set of gates we choose to start with.

**The Solovay–Kitaev Theorem.**
Choose any two universal sets of gates that are **weakly** closed under inverses (that is, the inverse of any gate in the set can be constructed (exactly) as a *finite* sequence of gates in the set, even if it is not itself an elementary gate).
Then any

Since errors accumulate linearly, it suffices to approximate each gate from one set to accuracy *can we get close to this lower bound*?
In general, we do not know.
However, for some universal sets of gates we have *nearly* optimal constructions.
For example, the set *single-qubit* unitaries to accuracy

Counting arguments nearly always use

**binomial coefficient**notation:\binom{a}{b}\coloneqq\frac{a!}{b!(b-a)!} .↩︎