In the paper by Dawson and Nielsen where they develop an algorithm for the Solovay-Kitaev Theorem, they analyze the lenght of the output noting how, for an approximation of degree $n$, the lenght of the output sequence is $5l_{(n-1)}$ where $l_{(n-1)}$ is the lenght of the sequence for the approximation of degree $n-1$. They conclude that the algorithm produces a sequence asymptotically of lenght $O(5^n)$.
We can then work on the recurrence for the approximation error $\epsilon_n$, and by isolating $n$ we arrive at this formula: $$n = \left \lceil {\frac{\ln\left(\frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \cdot c_{appr}^2)}\right)}{\ln\left(\frac{3}{2}\right)}}\right \rceil $$
Then they affirm how substituting the right hand side of this formula into $O(5^n)$ allows us to rewrite it in terms of $\epsilon$ to get the result stated in the theorem of page 4 of the paper: $O\left(\ln\left(\frac{1}{\epsilon}\right)^{3.97}\right)$, but I don't get wich passages we need to perform to arrive at such conclusion. Can anyone help me?
Thank you.


1 Answer 1


They use the rule of conversion of logarithms: $$ \log_b x = \frac{\log_c x}{\log_c b}.$$

For clarity define the following quantity: $$ A:= \frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \cdot c_{appr}^2)}. $$ Now we can write $$ n = \left \lceil {\frac{\ln \left( \frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \cdot c_{appr}^2)} \right)}{\ln(3/2)}}\right \rceil = \left \lceil {\frac{\ln(A)}{\ln(3/2)}}\right \rceil. $$

We use the log conversion rule to rewrite $\ln(A)$: $$ \ln(A) = \frac{\log_5 A}{\log_5 e}. $$ So we get $$ n = \left \lceil {\frac{\frac{\log_5 A}{\log_5 e}}{\ln(3/2)}}\right \rceil. $$ Now, substitute the above equation into $O(5^n)$ and ignore the ceiling operation with the Big $O$: $$ 5^n = 5^{\frac{\frac{\log_5 A}{\log_5 e}}{\ln(3/2)}} = \left ( 5^{\log_5 A} \right)^{\frac{\frac{1}{\log_5 e}}{\ln(3/2)}} = (A)^{\frac{\frac{1}{\log_5 e}}{\ln(3/2)}}. $$ Next, we use the log conversion again to rewrite $\log_5 e$ as follows: $$ \log_5 e = \frac{\ln e}{\ln 5} = \frac{1}{\ln 5}. $$ Hence, we can write $$ 5^n = (A)^{\frac{\ln 5}{\ln(3/2)}}. $$ So, we have $$ 5^n = (A)^{\frac{\ln 5}{\ln(3/2)}} = \left( \frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \cdot c_{appr}^2)} \right)^{\frac{\ln 5}{\ln(3/2)}}. $$

Note that $\ln(1/\epsilon_0 \cdot c_{appr}^2)$ is constant in $\epsilon$, so it will disappear when we push it through Big $O$. Also, we can absorb the constant $c^2_{appr}$ into $\epsilon$. Therefore, we get the final result: $$ l_{\epsilon} = O\left( \ln(1/\epsilon ) ^{\frac{\ln 5}{\ln(3/2)}} \right). $$ We also have $\frac{\ln 5}{\ln(3/2)} \approx 3.97$. So we get the result in the theorem: $$ l_{\epsilon} = O\left( \ln(1/\epsilon ) ^{3.97} \right). $$

We can do the same thing for $O(3^n)$ to get : $$ t_{\epsilon} = O\left( \ln(1/\epsilon ) ^{\frac{\ln 3}{\ln(3/2)}} \right). $$ The above can also be written as presented in the theorem: $$ t_{\epsilon}= O\left( \ln(1/\epsilon ) ^{2.71} \right). $$


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.