Basic approximation in Solovay-Kitaev algorithm

Question

I read the Solovay-Kitaev algorithm for approximation of arbitrary single-qubit unitaries. However, while implementing the algorithm, I got stuck with the basic approximation of depth 0 of the recursion.

Can someone help me on how to implement the basic approximation such that, given any $2 {\times} 2$ matrix in $\operatorname{SU}\left(2\right)$, it will return the sequence of gates from the set $\left\{H,T,S\right\}$ which approximate to about 0.00001 trace-norm distance of the arbitrary matrix?

Also, if I am using brute-force or kd trees, up to what gate length $l_0$ should I consider to obtain initial approximation of $0.00001$ for any arbitrary matrix in $\operatorname{SU}\left(2\right)$?

Answer 1

I don't pretend that this is optimal in the sense of minimal number of applications, but here's one method that comes from the universality proof...

• The unitary that you want to implement can be parametrised by $U=\cos\gamma\mathbb{I}-i\sin\gamma\ \underline{m}\cdot\underline{\sigma}$ where $\underline\sigma$ is the vector of Pauli matrices $X$, $Y$, $Z$. If you don't know the values you can get them from e.g. $\cos\gamma=\text{Tr}(U)/2$, $\sin\gamma\ m_X=\text{Tr}(XU)/2$ and so on.
• You can implement two unitaries $HTHT=\cos\theta\mathbb{I}-i\sin\theta \underline{n}_1\cdot\underline{\sigma}=R_1(\theta)$ and $THTH=\cos\theta\mathbb{I}-i\sin\theta \underline{n}_2\cdot\underline{\sigma}=R_2(\theta)$. Make sure you know what $\theta$, $\underline{n}_1$ and $\underline{n}_2$ are.
• Your first goal is to work out how to express $U$, your target unitary, in the form $e^{i\alpha}R_1(\phi_1)R_2(\phi_2)R_1(\phi_3)$. Again, evaluate things like $\text{Tr}(U),\ \text{Tr}(\underline{n_1}\cdot\underline{\sigma} U)$, but using the new decomposition, and you'll have a set of 3 simultaneous equations to solve for 3 parameters. For example (you'll need to check these!), $$ e^{i\alpha}\cos\gamma=\cos\phi_2\cos(\phi_1+\phi_3)-\sin\phi_2\sin(\phi_1+\phi_3)\underline{n}_1\cdot\underline{n}_2\\ e^{i\alpha}\sin\gamma \underline{m}\cdot\underline{n}_1=\cos\phi_2\sin(\phi_1+\phi_3)-\sin\phi_2\cos(\phi_1+\phi_3)\underline{n}_1\cdot\underline{n}_2 $$
• Now, you want to create a good approximation to the angle $\phi_i$, but you can only repeat sequences such as $HTHT$ an integer number of times, $q_i$. Thus we can create angles $q_i\theta$, but angles are only important modulo $2\pi$. Thus, for each $\phi_i$, find the smallest positive integer $q_i$ such that $|q_i\theta \text{ mod }2\pi-\phi_i|<\epsilon$ for some small parameter $\epsilon$. This means that by repeating $HTHT$ $q_3$ times, then $THTH$ $q_2$ times, then $HTHT$ $q_1$ times, you create each of the 3 rotations about the correct axis, to an angle that is within $\epsilon$ accuracy for each.
• You final task is to work out how the accuracy $\epsilon$ on each angle corresponds to an overall accuracy on the unitary If you think about a perturbative expansion of each term, the error is probably about $3\epsilon$. So, now you can work backwards to find $\epsilon$ and know what you need.