I am currently looking into quantum compilation and came across Dawson and Nielsen's paper on the Solovay-Kitaev Algorithm, which seems like a good starting point as it is referenced in a many of the papers on the subject. I have a working (although inefficient) implementation of a Basic Approximation which I plan to improve on using k-d trees.

I am, however, not confident I have properly understood aspects of the implementation of GC-Decompose which aims to decompose a matrix we'll call $U$ into a (balanced) group commutator $VWV^{\dagger}W^{\dagger}$ for some $V$ and $W$ with a distance to $I$ bounded by $c_{cg}\sqrt{\epsilon}$. My broad understanding of the method so far is:

  • Assume $V$ is a rotation by an angle $\phi$ about the $\hat{x}$ axis and $W$ is a rotation by the same angle $\phi$ about the $\hat{y}$ axis.
  • The composition of these two rotations is a rotation about another axis $\hat{n}$ on the Bloch sphere by an angle $\theta$ such that $\sin(\theta / 2) = 2 \sin^2(\phi/2) \sqrt{1- \sin^4(\phi/2)}$.
  • If $U$ represents a rotation by an angle $\theta$ around some axis $\hat{p}$ then it can be expressed as:
    1. A rotation from $\hat{p}$ to $\hat{n}$. In the paper the rotation from $\hat{p}$ to $\hat{n}$ is given by a unitary matrix $S$.
    2. A rotation about $\hat{n}$ by $\theta$ which is equivalent to $VWV^{\dagger}W^{\dagger}$ where $V$ is a rotation about the $\hat{x}$ axis by an angle $\phi$ and $W$ is a rotation about the $\hat{y}$ axis also by $\phi$ where $\phi$ and $\theta$ are related by the above equation.
    3. A rotation back to $\hat{p}$. As this is simply the inverse of (1.) this is $S^{\dagger}$.
  • Therefore $U = S(VWV^{\dagger}W^{\dagger})S^{\dagger}$ which can be expressed as $U = \tilde{V}\tilde{W}\tilde{V}^{\dagger}\tilde{W}^{\dagger}$ where $\tilde{V}\equiv SVS^{\dagger}$ and $\tilde{W}\equiv SWS^{\dagger}$.

According to my understanding above, I would expect the steps for computing a balanced group commutator for $U$ to be:

  1. Find the angle of rotation $\theta$ corresponding to $U$. (Any pointers on how to do this would be greatly appreciated)
  2. Find an angle $\phi$ satisfying $\sin(\theta / 2) = 2 \sin^2(\phi/2) \sqrt{1- \sin^4(\phi/2)}$.
  3. Find $S$ such that $U = S(VWV^{\dagger}W^{\dagger})S^{\dagger}$ where $V$ is a rotation about $\hat{x}$ by $\phi$ and $V$ is a rotation about $\hat{y}$ by $\phi$. Again I am not sure how this would be "easily computed". The introduction to Nagy's paper 'On an implementation of the Solovay-Kitaev algorithm' mentions that the method for SU(d) involves diagonalization, however, I can't convince myself that $VWV^{\dagger}W^{\dagger}$ is diagonal.
  4. Return $\tilde{V} = SVS^{\dagger}$ and $\tilde{W} = SWS^{\dagger}$.

Is this correct?

Apologies if I have completely misunderstood or missed something obvious. I am relatively new to a lot of the terminology in the paper so it is quite possible that I am on completely the wrong track.

  • $\begingroup$ V and W are taken to be $\sqrt{\epsilon_{n-1}}$ away from $I$ perhaps this can be thought of as a reasonable answer to why the group commutator would be diagonal $\endgroup$ Mar 7, 2022 at 18:08
  • 1
    $\begingroup$ In case it helps, I put a working implementation here. $\endgroup$
    – rhundt
    Apr 3, 2023 at 1:07


Your Answer

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