# Solovay-Kitaev Balanced Group Commutators in SU(2) Implementation

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.

• 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 Mar 7, 2022 at 18:08
• In case it helps, I put a working implementation here. Apr 3, 2023 at 1:07