Understanding the length of the sequence obtained via Solovay-Kitaev decomposition

Question

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:

SHTHTHTHTHHTHTHTHTHTHTHHTHhthhththththshthhththththtSTHTHSHTHSHTHTHTHTHHTHTHTHHTHTHTHTHSHTHhthththhththththshththththTHTHSHHSTHTHShthshthshthtsTHTHTHTHTHHTHSHTHTHTHTHHTHhthhththththththhththththsshthtshhshthtHTHTHTHTHSHTHTHTHTHHTHTHTHhthshththththhthththhththtTHTHSHTHSHTHSTHSSTHTHSTHHHshthshthshththhhtshthtsshtHHTHTHHHHTHSH

ACCURACY 0.053661016216388954

So I just want to know why?

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.