If I understand correctly, there must exist unitary operations that can be approximated to a distance $\epsilon$ only by an exponential number of quantum gates and no less.
However, by the Solovay-Kitaev theorem, any arbitrary unitary operation in $n$ qubits, with $n$ fixed, can be approximated to a distance of $\epsilon$ using poly(log(1/$\epsilon$)) universal gates.
Don't these two statements appear contradictory? What am I missing?
Note that Solovay-Kitaev theorem holds for unitaries on qu$d$it (section 5 in DN05), then we can set $d=2^n$ for $n$-qubit unitary. Following the same analysis, we obtain
Now the issue is the accuracy parameter $\epsilon$. Since $SU(d)$ is $(d^2-1)$-dimension manifold, so to approximate every gate in $SU(d)$ within $\epsilon_0$, we generate $O(1/\epsilon_0^{d^2-1})$ sequences.
Hence, for any specific universal gate set $\mathcal{G}$ the length of gate sequences $$l_0 \geq O\left(\frac{d^2-1}{\log |\mathcal{G}|} \log(1/\epsilon_0)\right).$$ Set $d=2^n$ for $n$ qubits, then we obtain $l_0 \sim 4^n \mathrm{poly}\log(1/\epsilon)$. Therefore, you indeed need exponentially many gates for approximating unitaries on $n$ qubits.
The full scaling will be $O(4^n\text{poly}\left(\log\frac{1}{\epsilon}\right))$, so you do indeed get exponential scaling in the number of qubits.
