1
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

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

Your Answer

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

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