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