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)$?


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.
  • 1
    $\begingroup$ You seem to call $U$ two different things, bullets 1 and 3. In bullet 4 not clear what $\phi_i$ has to do with $\theta$ and $q_i$ $\endgroup$ – rrtucci Jul 5 '18 at 16:18
  • $\begingroup$ @rrtucci I have just parametrised $U$ in two different ways. I was intending to connect the two, except that the expressions are horrible, so I aborted! $\endgroup$ – DaftWullie Jul 5 '18 at 18:02
  • 2
    $\begingroup$ DaftWullie, it's excellent answer, just trying to make you clarify that U and theta same throughout. Maybe if say in third bullet, "express U in the form" instead of "express U=" $\endgroup$ – rrtucci Jul 5 '18 at 18:24
  • 1
    $\begingroup$ @DebarghyaKundu Argh! Thanks for spotting that. Something must have slipped in the previous edit. $\endgroup$ – DaftWullie Jul 9 '18 at 9:20
  • 1
    $\begingroup$ @DebarghyaKundu there's a small trick using the cyclic properties of the trace, so $\text{Tr}(R_1(\phi_1)R_2(\phi_2)R_1(\phi_3))=\text{Tr}(R_2(\phi_2)R_1(\phi_3)R_1(\phi_1))=\text{Tr}(R_2(\phi_2)R_1(\phi_1+\phi_3))$. Now, when you multiply out these terms, each one either gives $\mathbb{I}$ or a Pauli matrix. The Pauli matrices have trace 0, so you're just looking for $\mathbb{I}$ terms. These are when the $\mathbb{I}$ terms meet, or identical pairs of Paulis meet (in the first statement, there are no 3-body terms that could also contribute). $\endgroup$ – DaftWullie Jul 9 '18 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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