# Explicit Conversion Between Universal Gate Sets

I'm interested in the conversion between different sets of universal gates. For example, it is known that each of the following sets is universal for quantum computation:

1. $$\{T,H,\textrm{cNOT}\}$$
2. $$\{H,\textrm{c}S\}$$, where $$S=T^2$$ and $$S^2=Z$$, and $$\mathrm{c}S = \lvert 0 \rangle\!\langle 0 \rvert {\,\otimes\,} \mathbf 1 + \lvert 1 \rangle\!\langle 1 \rvert {\,\otimes\,} S$$.
3. $$\{H,\textrm{ccNOT}\}$$, where $$\textrm{ccNOT}$$ is also known as the Toffoli gate. Note that this case requires the introduction of an extra ancilla bit that records whether each of the amplitudes is real or imaginary, so that the entire computation only uses real amplitudes.

Now, let's say I've proven that the first set is universal. How can I write this set in terms of gates from the other sets? (It is possible that it is not possible perfectly.) The problem is that the other two cases are proven using a denseness in a particular space argument (here and here, much as you would use between $$H$$ and $$T$$ to generate arbitrary single-qubit rotations for the first set), each using a different subspace, and not by converting from one set to another. Is there an exact, direct conversion?

The particular sticking points are:

• (2 to 1): creating $$T$$ from controlled-$$S$$ and $$H$$. I could also accept creating any single-qubit phase gate that is not $$S$$, $$Z$$ or $$S^\dagger$$.
• (3 to 1): creating a controlled-Hadamard from $$H$$ and Toffoli. (Controlled-Hadamard is the equivalent of $$T$$ if the target is the ancilla qubit.) Alternatively, Aharonov gives us a way to convert 3 to 2, so the (2 to 1) step would be sufficient.

For reference, section 4 of this paper seems to make some steps related to achieving the (3 to 1) case, but in aiming for generality, pedagogy has perhaps fallen by the wayside slightly.

# Update

I recently came across this paper which essentially gives a necessary and sufficient condition for a given single-qubit unitary to be expressible in terms of a finite sequence of $$H$$ and $$T$$ gates. Building similar results for the other gate sets (e.g. necessary and sufficient condition for creating a two-qubit gate from $$H$$ and $$cS$$) would be a rigorous way of resolving this question one way or another.

• So basically, you don't want to use arguments like $HTH = R_x(\pi / 4)$ right? – cnada Aug 31 '18 at 17:18
• @cnada That's exactly what I want to do, but I'm trying to use the gates from (2) or (3) to make the gates in (1) not the other way around. I know how the gates in (1) can make the gates in (2) or (3). – DaftWullie Aug 31 '18 at 17:23
• I tried to use lemma 5.5 from arXiv:quant-ph/9503016. But could not do it. You basically try to find matrices A and B such that AB=I and AXB = H. I was thinking if we have them, we can see how we decompose them but that may be tough. – cnada Aug 31 '18 at 18:47
• @cnada It's easy enough to identify A and B in that scenario ($\pm3\pi/8$ rotations about the Y axis, I believe). The problem is how do you make that single-qubit rotation with the available gates. – DaftWullie Aug 31 '18 at 19:15
• @NtwaliB. The general solution is that you usually have to do things with long sequences of gates and create arbitrarily accurate approximations. This is probably part of the universality proof for your gate set. My question was about whether specific gates could be realised perfectly with a finite sequence, which I suspect is not the case, and it certainly won't be true in a general case. – DaftWullie Sep 18 '18 at 14:47

To fix what we are talking about, I think you mean $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \quad S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \quad T = \begin{pmatrix} 1 & 0 \\ 0 & \exp(i\pi/4) \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & \frac{1+i}{\sqrt{2}} \end{pmatrix}.$$ If these are your matrices, then no, you can't make gate set 1 from gate set 2. Let's look at these gates in superoperator form, i.e., as matrices acting on density matrices, so that we ignore global phase as we should. Then all of the entries of the superoperator forms of $$H$$ and $$S$$, call them $$\mathcal{H}$$ and $$\mathcal{S}$$, lie in the field of Gaussian rationals $$\mathbb{Q}(i)$$. In other words, the entries of these matrices are complex numbers whose real and imaginary parts are rational numbers. The same is true of the controlled $$S$$ gate. Two other quantum maps or superoperators that are important for the question are ancilla creation and qubit discard (or partial trace), and both of these also have all entries in $$\mathbb{Q}(i)$$. This property is also preserved when you either tensor or compose superoperators to make a circuit out of gates.
The superoperator form $$\mathcal{T}$$ of the gate $$T$$ does not have entries in $$\mathbb{Q}(i)$$. The field of definition for those numbers is instead $$\mathbb{Q}(i,\sqrt{2})$$. Thus $$\mathcal{T}$$ is unreachable by a finite circuit of $$H$$ and $$cS$$ gates (and creation and destruction of ancillas). Although as you note, the Solovay-Kitaev theorem says that every gate under the sun, or at least every gate with efficiently computable matrix entries, can be efficiently approximated.
Finally, where you say that you could also accept creating any new phase gate, in fact, the only phase gates that are reachable using gate set 2 are those that are powers of $$S$$, although you have to do a bit more work than to trap the superoperator matrix entries in $$\mathbb{Q}(i)$$. In fact the superoperator entries of the gate 2 set or any circuit made from it are all Gaussian integers, elements of $$\mathbb{Z}[i]$$, except for a global denominator to make the superoperator trace-preserving. The only Gaussian integers that lie on the unit circle are $$\pm 1$$ and $$\pm i$$.