Decomposition of an arbitrary 1-qubit gate into a specific gateset

Question

Any 1-qubit special gate can be decomposed into a sequence of rotation gates ($R_z$, $R_y$ and $R_z$). This allows us to have the general 1-qubit special gate in matrix form:

$$ U\left(\theta,\phi,\lambda\right)=\left(\begin{array}{cc} e^{-i(\phi+\lambda)}\cos\left(\frac{\theta}{2}\right) & -e^{-i(\phi-\lambda)}\sin\left(\frac{\theta}{2}\right)\\ e^{i(\phi-\lambda)}\sin\left(\frac{\theta}{2}\right) & e^{i(\phi+\lambda)}\cos\left(\frac{\theta}{2}\right) \end{array}\right) $$

If given $U\left(\theta,\phi,\lambda\right)$, how do I decompose it into any arbitrary set of gates such as rotation gates, pauli gates, etc?

To make the question more concrete, here is my current situation: for my project, I am giving users the ability to apply $U\left(\theta,\phi,\lambda\right)$ for specific values of $\theta$, $\phi$ and $\lambda$ to qubits.
But I am targeting real machines that only offer specific gates. For instance, the Rigetti Agave quantum processor only offers $R_z$, $R_x\left(k\pi/2\right)$ and $CZ$ as primitive gates.
One can think of any $U\left(\theta,\phi,\lambda\right)$ as an intermediate form that needs to be transformed into a sequence of whatever is the native gateset of the target quantum processor.

Now, in that spirit, how do I transform any $U\left(\theta,\phi,\lambda\right)$ into say $R_z$ and $R_x\left(k\pi/2\right)$? Let us ignore $CZ$ since it is a 2-qubit gate.

Note: I'm writing a compiler so an algorithm and reference papers or book chapters that solve this exact problems are more than welcome!

Answer 1

Exact decomposition for your particular gate set

Given the range of $R_x$ gates available to you together with arbitrary $R_z$ gates, you should be able to find an easy decomposition of arbitrary $R_y$ gates (i.e. as a product of three of your elementary gates). Then using simple techniques — similar to the exercises of Chapter 4 in Nielsen & Chuang — you can show that you can exactly realise any single-qubit unitary operator that you like, using at most five of your gates.

The general problem of approximate decomposition for finite gate-sets

In general, it may not be possible to decompose a single-qubit gate exactly, as a product of some other single-qubit gates. This is true even of 'universal' gate sets such as Hadamard+T, consisting of the gates $$ H = \tfrac{1}{\sqrt 2}\begin{bmatrix} 1 \!&\! \phantom-1 \\ 1 \!&\! -1 \end{bmatrix}, \qquad T = \begin{bmatrix} 1 & 0 \\ 0 & \!\mathrm{e}^{\pi i \!\:/ 4}\! \end{bmatrix}, $$ which of course can only generate a countably infinite subgroup of the continuum of single-qubit unitaries. The sense in which they are 'universal' is that this subgroup is dense in the single-qubit unitaries, so that any single-qubit unitary can be approximated as closely as you like by some product of H and T gates, which is all that we really need to solve problems with bounded error on quantum computers. So it makes sense to me, practically speaking, to interpret your question as asking:

Question. For a given single-qubit unitary $U$, how can you generate some approximating unitary $V$ (such that $\lVert U - V \rVert < \varepsilon$, for some precision parameter $\varepsilon > 0$) from a set of unitary gates?

• The best-known work on these lines was by Solovay [unpublished] and Kitaev [Russ. Math. Sure. 52 (1191–1249), 1997], and is known as the Solovay–Kitaev Theorem. The excellent review article by Dawson and Nielsen [arXiv:quant-ph/0505030] would be a good place to read about this from an algorithms point of view: they give a detailed description of how you might realise such a decomposition, with improved run-time bounds on the original Theorem. This technique only works if the set of gates that you have is closed under inverses, however.

• For specific gate sets such as Clifford+T (of which Hadamard+T is essentially the single-qubit special case), it is possible to do much better than the Solovay–Kitaev Theorem proves for general (but closed under inverses) gate sets. As Alan Geller points out in the comments, for the specific sets of Clifford+T, Clifford+(Z^1/6) or "Clifford+$\pi$/12" gates, and "Fibonacci" or "V" gates, the techniques developed by Kliuchnikov, Bocharov, Roetteler, and Yard [arXiv:1510.03888] allow you to obtain better asymptotically optimal $O(\log(1/\varepsilon))$ decompositions, and in $O(\mathrm{polylog}(1/\varepsilon))$ time, though depending in on a number theoretic conjecture in this case.