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?

  • 2
    $\begingroup$ In your statement, the number of gate is exponential with respect to what? The precision? $\endgroup$ Jul 26, 2018 at 17:33
  • 1
    $\begingroup$ I guess the number of qubits. I think I get it now. Keeping the precision fixed, there can be unitaries requiring an exponential number of gates to simulate, with respect to the number of qubits. In contrast, by the Solovay Kitaev theorem, keeping the number of qubits fixed, the number of universal quantum gates for simulation scales polynomially with respect to the precision. Is that what it is? $\endgroup$
    – BlackHat18
    Jul 26, 2018 at 17:43
  • 3
    $\begingroup$ Yes, exactly - you’re comparing scaling with respect to two different parameters: achievable accuracy for a single qubit gate as a function of the number of gates for some finite universal set, and the number of gates required to achieve a given accuracy for unitaries as a function of the number of qubits the unitary acts on. $\endgroup$
    – DaftWullie
    Jul 26, 2018 at 18:00
  • $\begingroup$ If the question is no longer being asked, @BlackHat18 could explain why as an answer themselves. What is the policy on this? $\endgroup$
    – AHusain
    Jul 27, 2018 at 21:52
  • 2
    $\begingroup$ @AHusain BlackHat18 self-answering is allowed and encouraged $\endgroup$
    – glS
    Jul 30, 2018 at 10:05

2 Answers 2


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

  • length of gate sequences $l_{\epsilon} = O(\ln^{\ln 5/\ln(3/2)} (1/\epsilon))$,
  • time complexity $t_{\epsilon} = O(\ln^{\ln 3/\ln(3/2)}(1/\epsilon))$.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.