Explicit Conversion Between Universal Gate Sets

Question

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.

Answer 1

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.

I don't entirely know what you mean in your description of gate set 3. However, I think that in any reasonable interpretation of that gate set, the same argument applies. Certainly if you take the gate set verbatim and ignore the fact that it only produces real matrices, then something sharper happens; in superoperator form, it only produces rational matrices.

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$.