Why is Deutsch's gate universal?

Question

(This is related to Exercise 4.44 in Nielsen and Chuang)

Deutsch quantum gate is basically a $iR_x(\alpha \pi)$ gate with two control qubits. The constant $\alpha$ is an irrational number that allows to perform any rotation $R_x (\theta)$ by sending $|11\rangle$ to the control qubits. In particular, one can (approximately) construct the set $\{ X, CNOT, \text{Toffoli} \}$ by choosing

$$\alpha \pi \, \approx \, \pi \mod 2\pi,$$

such that $R_x(\alpha \pi) \approx X$. My question is: how do you reach quantum universality? I guess you should be able to construct the Hadamard ($H$) and phase ($S$) gates, which together with $CNOT$ and Toffoli give quantum universality. Or else you should be able to construct $R_z(\theta)$ since $R_z(\alpha) R_x(\beta) R_z(\gamma)$ or $R_x(\alpha) R_z(\beta) R_x(\gamma)$ give any one-qubit unitary.

Answer 1

I have thoughts on a couple of different approaches, although I'm sure there'll be simpler options.

Firstly, imagine you start from a two-qubit state $|00\rangle$, and apply an $R_x$ rotation with an angle equivalent to half that of a Pauli $X$ to the first qubit (I forget which convention N&C is using for their rotation gates). Then apply a controlled-not controlled off the first qubit and targeting the second qubit. Next, apply the inverse of the first rotation. Finally, measure the first qubit. If you get answer $|1\rangle$, the second qubit is in the $|-\rangle$ state. If it isn't, discard and repeat. So, we can produce the $|-\rangle$ state. If you input this as the target qubit of the controlled-controlled-$R_x$ (of arbitrary rotation angle), and have one of the controls in the $|1\rangle$ state, you get an arbitrary $Z$ rotation on the other control qubit.

So, we know we can do arbitrary $X$ and $Z$ rotations, meaning that you can make any single-qubit unitary. Combine that with controlled-not and you know you have universality.

A second approach that I had in mind (I've not worked out the details) is to go for encoded universality, in much the same way as you can use to show that computation with real amplitudes is universal. To sketch the idea: for a computation on $N$ logical qubits, you need $N+1$ physical qubits. The extra qubit is a phase register, so if you have $|x\rangle(\cos\theta|0\rangle+\sin\theta|1\rangle)$, that is equivalent to $e^{i\theta}|x\rangle$ in a regular quantum computation (this is the real computation version. I think the definition will need to change slightly here). Now $X$ rotations and controlled-nots are performed exactly as they normally would be in the first $N$ qubits. However, a phase gate is now implemented by a controlled-$X$ rotation, controlled of the qubit that's supposed to be acquiring the phase, targeting the phase qubit. If you can achieve that set of gates, you should be able to compose that for universality.

Answer 2

A classical proof involves Lie algebra to show that the Deutsch's three Qubits gate is universal for three qubits gates and then showing that we can construct a $ n $ qubits Deutsch's gate using Toffoli gates and three qubits Deutsch's gate only, so the results extends to $n$ qubits.

You can find the proof in the caltech's course on quantum computation, page 29 to page 33. It's not an easy read (I mostly don't get it), but it seems complete. I hope it helps.

Another lead going your way would be to prove that a combination of Deutsch's three qubits gate can reproduce the Hadamard gate as the set $\{H, T\}$ (with $H$ for Hadamard and $T$ for Toffoli) is universal (proof in A Simple Proof that Toffoli and Hadamard are Quantum Universal by Dorit Aharonov). However I'm not able to tell if a combination of Deutsch's three qubits gate can give a Hadamard gate, it's only speculative.