# How to decompose a unitary single qubit gate by universal quantum gate set?

How to decompose a unitary single qubit gate? I have read some paper or books, which told me a unitary single qubit gate could be decomposed by universal quantum gates set. For example {phase gate, Hadamard gate} is one of them. But they don't tell me how to do. I just understand the method of decomposition is exist, but I don't know how to decompose. The existence is proved by Solovay–Kitaev theorem, and some paper also show that {phase gate, Hadamard gate} can be used as a universal quantum gate set. But is there a pratical method to solve "how to use {phase gate, Hadamard gate} to decompose a single qubit quantum gate? I want to know about the specific procedure.For example, How to use {phase gate, Hadamard gate} to decompose Pauli Z ?

The phase gate, $$S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix}$$ is just the square root of Pauli Z, so the specific decomposition in your question is nothing more than $$Z = SS$$.

The Hadamard gate can be used, for example, with Z to decompose Pauli X as $$X = HZH$$, which is an eigendecomposition of X. So if by chance you didn't have S, but had $$\lbrace X, H \rbrace$$ instead, you could get Z from $$Z=HXH$$.

As a practical matter, finding decompositions of arbitrary unitary gates into a discrete set of universal gates is not straightforward. In fact, as far as I know, finding the theoretical limit of the Solovay-Kitaev theorem is still an open problem. Section 4.5 of Nielsen and Chuang gives a good overview if you're looking for a solid foundation in the basic principles.

• Thx, have you ever read this paper arxiv.org/pdf/1206.5236.pdf, it told me he found a specific sequence of universal set, but actual I still do not get it. Lol – Henry_Fordham Jun 4 at 4:53
• @Henry_Fordham The early parts of that paper deal with exact decompositions of unitary matrices with entries in certain ring extensions (i.e. exact decompositions of a discrete subset of unitary matrices into a discrete set of gates). The latter sections deal with approximate decompositions of arbitrary unitary matrices into a discrete set of gates, which is a specific implementation of the Solovay-Kitaev algorithm. Feel free to ping me in chat if you have general questions on the paper you want to talk through. – Jonathan Trousdale Jun 4 at 14:15
• I saw the complexity of SK algorithm is O(log 3.97 1/accuracy), so what is that mean? does it means if i want to achieve accuracy equal to 0.01, then I need (log 3.97 100) gates in total to decompose a unitary single gate? but this is confusing, for example, I want to achieve same accuracy of 1/32 pi and 1/64 pi, the number of the gates which used to decompose surely couldn't be the same.. – Henry_Fordham Jun 6 at 0:38

You need to be a little careful with terminology. When you say "phase gate", what precisely do you mean? Often, that terminology refers to the gate $$S=\sqrt{Z}$$. In this context, I am assuming this is not what you mean because $$S$$ and $$H$$ are not universal for single-qubit gates. However, for completeness, you were asking how to make $$Z$$, which is trivial: $$Z=S^2$$.

You might mean an arbitrary phase gate $$R_z(\theta)=e^{iZ\theta/2}$$ where you can choose any/all $$\theta$$ values. In that case, your special case is $$Z=R_z(\pi)$$ (up to a global phase). You can decompose any arbitrary single-qubit unitary, making use of Euler angles (or just brute force) to give the decomposition $$U=e^{i\delta}R_z(\alpha)HR_z(\beta)HR_z(\gamma).$$ There are other questions.answers on this site with more details about how to find what the parameters are.

What you seem to imply in comments is that you're really interested in the set $$H$$ and $$T$$ ($$S=T^2$$). In that case, $$Z=T^4$$. If you want to find a good decomposition of an arbitrary single-qubit unitary in terms of $$H$$ and $$T$$, you need the Solovay-Kitaev algorithm. Dawson wrote quite a useful paper on how to do it.

More recent work has reduced the number of gates needed to synthesise the same unitary. Unless things have moved on, the way that I understand it working is that you first have to run the Solovay-Kitaev algorithm. This finds a good approximation of your unitary $$U$$ in the particular formulation required for an exact decomposition. It even gives you a sequence that makes it. But if you run Algorithm 1 from the Kliuchnikov et al. paper, that will give you a shorter sequence (guaranteed to be the shortest sequence up to some finite overhead). I find algorithm 1 to be pretty clear, it just leaves you with two technical problems: (i) evaluating the sde for a given unitary, and (ii) enumerating all the sde$$\leq 3$$ cases and how to make them. Persumably the code they provide could help you with those.