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:
- $\{T,H,\textrm{cNOT}\}$
- $\{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$.
- $\{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.