I have downloaded two codes of SK algorithm from GitHub and try to understand how to decompose a unitary single qubit gate. These code are https://github.com/DEBARGHYA4469/Quantum-Compiler and https://github.com/cryptogoth/skc-python. As SK algorithm needs two parameters - an unitary single qubit gate $U$ and deepth $n$. I tried to put $n=2$ and make a unitary qubit gate as $U$. If I set the accuracy $\epsilon = 0.125$, which means the sequence should include $O(\log 3.97\cdot 0.05)$ gates. I calculated it ($\log 3.97 \cdot 0.01$ is around 2). But actually the sequence I get from code is far more than 2 gates:


ACCURACY 0.053661016216388954

So I just want to know why?


1 Answer 1


According to the paper The Solovay-Kitaev algorithm (pg. 7) a number of single qubits gates approximating unitary $U$ is

$$ l = O(\ln^{\ln5/\ln(3/2)}\frac{1}{\epsilon}), $$

where ${\ln5/\ln(3/2)} = 3.97$. So, in your case with accuracy $\epsilon = 0.125$, you have $\ln^{3.97}\frac{1}{0.125}=\ln^{3.97} 8 = 18.29$.

For $\epsilon = 0.05$, you will get 77.93.

Moreover, a complexity of the algorithm is expressed in O-notation. This means that there can be a constant before expession in brackets. There is no limit on this constant, so it can be pretty big.

  • $\begingroup$ THANK you~~~~~~ $\endgroup$ Commented Jun 6, 2020 at 7:17

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.